文档介绍：第4章贪心算法1学****要点理解贪心算法的概念。掌握贪心算法的基本要素(1)最优子结构性质(2)贪心选择性质理解贪心算法与动态规划算法的差异理解贪心算法的一般理论通过应用范例学****贪心设计策略。(1)活动安排问题;(2)最优装载问题;(3)哈夫曼编码;(4)单源最短路径;(5)最小生成树;(6)多机调度问题。。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船。1、算法描述最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略,可产生最优装载问题的最优解。具体算法描述如下页。<classType>voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}、贪心选择性质 可以证明最优装载问题具有贪心选择性质。3、最优子结构性质 最优装载问题具有最优子结构性质。由最优装载问题的贪心选择性质和最优子结构性质,容易证明算法loading的正确性。算法loading的主要计算量在于将集装箱依其重量从小到大排序,故算法所需的计算时间为O(nlogn)。。其压缩率通常在20%~90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。 给出现频率高的字符较短的编码,出现频率较低的字符以较长的编码,可以大大缩短总码长。1、前缀码对每一个字符规定一个0,1串作为其代码,并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码。。表示最优前缀码的二叉树总是一棵完全二叉树,即树中任一结点都有2个儿子结点。平均码长定义为: 使平均码长达到最小的前缀码编码方案称为给定编码字符集C的最优前缀码。、构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法,由此产生的编码方案称为哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以|C|个叶结点开始,执行|C|-1次的“合并”运算后产生最终所要求的树T。,编码字符集中每一字符c的频率是f(c)。以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后,产生一棵新的树,其频率为合并的2棵树的频率之和,并将新树插入优先队列Q。经过n-1次的合并后,优先队列中只剩下一棵树,即所要求的树T。算法huffmanTree用最小堆实现优先队列Q。初始化优先队列需要O(n)计算时间,由于最小堆的removeMin和put运算均需O(logn)时间,n-1次的合并总共需要O(nlogn)计算时间。因此,关于n个字符的哈夫曼算法的计算时间为O(nlogn)。、哈夫曼算法的正确性要证明哈夫曼算法的正确性,只要证明最优前缀码问题具有贪心选择性质和最优子结构性质。(1)贪心选择性质(2)最优子结构性质10