实验二贪心算法.docVIP

实验二 贪心法（4学时） 上机实验一般应包括以下几个步骤： （1）、准备好上机所需的程序。手编程序应书写整齐，并经人工检查无误后才能上机。 （2）、上机输入和调试自己所编的程序。一人一组，独立上机调试，上机时出现的问题，最好独立解决。 （3）、上机结束后，整理出实验报告。实验报告应包括：题目、程序清单、运行结果、对运行情况所作的分析。 一、实验目的与要求 掌握贪心法的基本思想方法； 了解适用于用贪心法求解的问题类型，并能设计相应贪心法算法； 掌握贪心算法复杂性分析方法分析问题复杂性。 二、实验内容： 1、哈夫曼编码 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。设计贪心算法求解此哈夫曼编码方案； 2、删数问题 键盘输入一个高精度的正整数n（n10位）去掉任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数最小。 3、贪心背包问题 已知一个容量为M的包和n件物品, 每件物品的重量为wi, 效益值为pi. 若将物品i的一部分0≤xi≤1装入包中, 背包可得到pixi的效益值增量. 要求找到一种装入物品的方案, 在不超过包的总容量前提下, 使包获得最大效益值。 三、实验步骤 理解算法思想和问题要求； 编程实现题目要求； 上机输入和调试自己所编的程序； 验证分析实验结果； 整理出实验报告。 四、实验要求 1）上述题目任选两道做。 2）独立完成程序代码的编写 3）独立完成实验及实验报告 附：实验报告的主要内容 一．实验目的 二．问题描述 三．解题思路 四．算法设计 包含：数据结构与核心算法的设计描述、函数调用及主函数设计、主要算法流程图等 五.程序调试及运行结果分析 六.实验总结 附录：程序清单 （程序过长，只附主要部分） 五、实验原理 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 A、贪心算法的基本思路 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 B、实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 C、贪心算法的适用的问题： 贪心算法适用的问题必须满足两个属性： （１） 贪心性质：整体的最优解可通过一系列局部最优解达到，并且每次的选择可以依赖以前做出的选择，但不能依赖于以后的选择。 （２） 最优子结构：问题的整体最优解包含着它的子问题的最优解。 D、贪心算法的基本步骤 （１） 分解：将原问题分解为若干相互独立的阶段。 （２） 解决：对于每一个阶段求局部的最优解。 （３） 合并：将各个阶段的解合并为原问题的解。 附注：部分实验代码 1、哈夫曼编码 数据结构与算法 typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 核心源代码 #include stdio.h #include stdlib.h #include string.h typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 //选择两个parent为0，且weight最小的结点s1和s2 void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(