第4章 贪心算法(1-例子)

《第4章 贪心算法(1-例子)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、4.34.3最优装载最优装载有一批集装箱要装上一艘载重量为有一批集装箱要装上一艘载重量为cc的轮船。其的轮船。其中集装箱中集装箱ii的重量为的重量为WiWi。最优装载问题要求确定在。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。装上轮船。11、算法描述、算法描述最优装载问题可用贪心算法求解。采用重量最优装载问题可用贪心算法求解。采用重量最最轻者先装轻者先装的贪心选择策略，可产生最优装载问题的的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。最优解。具体算法描述如下

2、页。14.34.3最优装载最优装载templatevoidLoading(intLoading(intx[],Typew[],Typec,intintn){intint*t=newintint[n+1];Sort(w,t,n);for(intinti=1;i<=n;i++)x[i]=0;for(intinti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}24.34.3最优装载最优装载22、贪心选择性质（书、贪心选择性质（书P108P108））可以证明最优装载问题具有贪心选择性质。

3、可以证明最优装载问题具有贪心选择性质。33、最优子结构性质（书、最优子结构性质（书P108P108））最优装载问题具有最优子结构性质。最优装载问题具有最优子结构性质。由最优装载问题的贪心选择性质和最优子结构性由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法质，容易证明算法loadingloading的正确性。的正确性。算法算法loadingloading的主要计算量在于将集装箱依其重量的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为从小到大排序，故算法所需的计算时间为O(nlognO(nlogn))。。34.34.3最优

4、装载最优装载44.34.3最优装载最优装载54.34.3最优装载最优装载思考：思考：最优装载问题，若推广最优装载问题，若推广至两艘船，贪心算法仍然能得到至两艘船，贪心算法仍然能得到最优吗？最优吗？此推广即为：书P1435.2的装载问题贪心算法已不能产生最优解，这和0-1背包问题类似，因为贪心选择并不能保证第一艘船装满，而第一艘船的剩余空间应该越小越好。64.44.4哈夫曼编码哈夫曼编码哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的十分是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在有效的编码方法。其压缩率通常在20%20%～～90%90%

5、之间。之间。哈夫曼编码算法用字符在文件中出现的频率表来建哈夫曼编码算法用字符在文件中出现的频率表来建立一个用立一个用00，，11串表示各字符的最优表示方式。串表示各字符的最优表示方式。给出现频率高的字符较短的编码，出现频率较给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。低的字符以较长的编码，可以大大缩短总码长。11、前缀码、前缀码对每一个字符规定一个对每一个字符规定一个0,10,1串作为其代码，并要串作为其代码，并要求任一字符的代码都求任一字符的代码都不是不是其它字符代码的前缀。其它字符代码的前缀。这种编码称为这种

6、编码称为前缀码前缀码。。74.44.4哈夫曼编码哈夫曼编码编码的前缀性质可以使译码方法非常简单。编码的前缀性质可以使译码方法非常简单。因为树有这样结构特性：任何一个从根到某一树因为树有这样结构特性：任何一个从根到某一树叶的路径都不是根到其他叶子的路径的一部分。叶的路径都不是根到其他叶子的路径的一部分。84.44.4哈夫曼编码哈夫曼编码表示表示最优前缀码最优前缀码的二叉树总是一棵的二叉树总是一棵完全二叉完全二叉树树，即树中任一结点都有，即树中任一结点都有22个儿子结点。个儿子结点。平均码长平均码长定义为：定义为：B(T)f(c)dT(c)cC使平

7、均码长达到最小的前缀码编码方案称为给使平均码长达到最小的前缀码编码方案称为给定编码字符集定编码字符集CC的的最优前缀码最优前缀码。。94.44.4哈夫曼编码哈夫曼编码22、构造哈夫曼编码、构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为产生的编码方案称为哈夫曼编码哈夫曼编码。。哈夫曼算法以自底向上的方式构造表示最优前哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树缀码的二叉树TT。。算法以算法以

8、C

9、

10、C

11、个叶结点开始，执行个叶结点开始，执行

12、C

13、

14、C

15、－－11次的次的““合合并并”

16、”运算后产生最终所要求的树运算后产生最终所要求的树TT。。104.44.4哈夫曼编码哈夫曼编码114.44.