算法课后作业参考答案第四章

1、第四章 贪心算法算法分析题：课后作业4-1（此为第三版书的 4-1 题）在活动安排问题中，还可以有其它的贪心选择方案，但并不能保证产生最优解。给出一个例子，说明若选择具有最短时段的相容活动作为贪心选择，得不到最优解。若选择覆盖未选择活动最少的相容活动作为贪心选择，也得不到最优解。参考解答：这两个贪心选择方案都不能得到最优解的，反例在上课的课件上。活动系列：最优解1,2,3,4，4 个相容活动。若选择具有最短时段的相容活动作为贪心选择，则选择为1,4,5。只有 3 个相容活动，不是最优解。若选择覆盖未选择活动最少的相容活动作为贪心选择，必初选 5，5 一旦选中，最多只能再选两个。最多只有 3 个

2、相容活动，也不是最优解。4-3（此为第三版书的 4-3 题）在 0-1 背包问题中，各物品依重量递增排列时，其价值恰好递减排列。对这个特殊的 0-1 背包问题，设计一个有效算法找出最优解，并证明算法的正确性。参考解答：共 n 件物品， w，背包容量 C。根据题意，不妨设：0 w1 w2 wn ， v1 v2 vn 0v： iwivi1,1 i n 1 wi11、算法描述当物品未排好序时，将物品按照重量递增序排序（其实，也就是按照价值递减序排序），当物品已按重量排好序了，此步略过；按照前一步排序后的物品顺序，依次挑选物品进背包，直到装不进背包为止。这个算法第一步需要 O(nlogn)，第二步需要

3、 O(n)。因此整个算法需要 O(nlogn)的计算时间。2、算法正确性证明先此特殊 0-1 背包问题的贪心选择性质：当 w1 C 时，问题无解。当 w1 C 时，此时的贪心选择性质就转化为证明：存在这个特殊 0-1 背包问题的一个最优解 S 1,2,., n，S 为 n 个物品集合的一个子集，且1 S 。若 S 1,2,., n 是特殊 0-1 背包问题的一个最优解，且1 S ，对 i S ， 令Q S 1 i，且有 w1 wi 。则： wj wj w1 wi CjQ jS 因此， Q S 1 i 是此特殊 0-1 背包问题的一个可行解。另外，vj vj v1 vi vj（1）jQjS jS

4、 又由于之前假设 S 是一个最优解，故vj v j（2）jSjQ 结合不等式（1）和不等式（2），有v j vj ，故Q S 1 i 也是一个 最优jSjQ 解，又Q 满足贪心选择性质，因此Q 是一个满足贪心选择性质的最优解，又由于所有的 0-1背包问题具有最优子结构性质（这一性质在书上 P106 有叙述，这里不再累述），因此贪心算法的正确性得证。4-2 参考解答：最优装载问题若推广至两艘船（第一艘船和第二艘船载重量为 c1 和 c2），要看这问题怎么问？这个问题分析起来其实很复杂啊。在 OJ 系统上已经增加了一题“17097 两艘船的装载问题”，用测试数据对这个问题来举例说明。点评：在大家作

5、业中仅看见很少的几位同学对这道题有展开分析的，大多数同学都千篇一律的回答，比如“不能采用贪心算法”，“应该尽可能将第一艘船装满”等这样的回答。n i i1c ，是否有方案能将 n 个箱子装上两艘船？（1）n 个箱子，且n ic ，所以，两艘船上必然有剩余空间，这完全就是书上 5.2 这个例子，因为i1那让部分的箱子上第一艘船且尽可能接近 c1，使第一艘船剩余空间尽可能小（即第一艘船尽可能满但不超过 c1），剩下的集装箱再装上第二艘船，如果可以装上第二艘船，则可以将这 n 个箱子装上两艘船。但若剩下的箱子不能全装上第二艘船，请大家思考一下，是否就可以说明这个问题无满足的方案？我认为应该再尝试一下

6、“先尽可能把第二艘船装满（最接近 c2），剩下看看能否装上第一艘船？”（2）n 个箱子，能否尽可能多的将箱子装上两艘船？（指所有装上船的箱子的数量），如何能装上尽可能多的箱子呢？若还按照较轻的箱子先装这样的贪心算法就不一定能产生最优解了。比如：若 10件箱子，分别：10 10 10 15 15 15 20 20 30 40，两艘船载重量分别为 70 和 50，若还按较轻者先装，则 10+10+10+15+15=60 装入第一艘船，15+20=35 装入第二艘船，共 7 个箱子。而这个问题的最优解，有多种方法可以装到 8 个箱子，比如，10+10+10+15+20=65 装入第一艘船，15+15

7、+20=50 装入第二艘船去，则总共装上 8个箱子。若尽可能将第一艘船装满这个策略也是的，比如，14 个箱子，分别：54 53 2 22 2 2 2 2 2 2 2 2 2，两艘船载重量分别为：55 和 54。若尽可能将第一艘船装满，则选择 53+2 两个箱子装入第一艘船，54 装入第二艘船，共 3 个箱子。而这个问题有更好的解：54（上第一艘）+ 12*2（上第二艘），共 13 个箱子。有同学会想，是否能变换一下：先将第二艘船装满再尽可能满的装第一艘船，和之前先将第一艘船装满再尽可能满的装第二艘船，这两种情况进行比较，取装的较好的这种。这样想法也是的，还是前面 14 个箱子的例子，分别：54

8、 53 2 2 22 2 2 2 2 2 2 2 2，两艘船载重量分别为：55 和 54。倒过来先装第二艘船再装第一艘船的话，也是只能上 3 个箱子，而这个问题最优的 13 个箱子，是这两种装法都达不到的。总结一句：要获得上船的箱子总数量尽可能多，不能采用先尽可能将第一艘船装满再尽可能装满第二艘船，倒过来先装第二艘船也，或者两种情况求较大，这样也。这条路走不通了。当然，这里没有限制所有箱子重量和要小于等于两艘船的载重量 c1+c2 之和。若如前有这个条件，大家考虑一下是否可行，这里我没有继续考虑下去了。（3）n 个箱子，能否尽可能重的将箱子装上两艘船？（指所有装上船的箱子的重量和）此题若是变一

9、下问题的求解目标：n 个重量可能不等的箱子，如何装上两艘船，使得装上船箱子的重量之和为最大？考虑一下，如果也尽可能让第一艘船装满或尽可能让第二艘船装满，这样能达到最优目标吗？若 4 件箱子，分别：10 40 20 25，两艘船，载重量分别为：55 和 30。若先尽可能将第一艘船装满，选择 10+20+25 这几个箱子装入第一艘船，则第二艘船最多装 0。共 10+20+25=55 装入两艘船。若先尽可能将第二艘船装满，选择 10+20 这几个箱子装入第二艘船，则第一艘船最多装 40。共 40+10+20=70 装入两艘船。而这个问题有更优解：10+40 装入第一艘船，而 25 装入第二艘船，共

10、10+40+25=75装入两艘船。总结一句：以上的反例，说明这个问题考虑先将第一艘船尽可能装满，或考虑先将第二艘船尽可能装满，再或者两者取较优，这些考虑都。那（2）和（3）问题如何求解？其实无论最优目标是尽可能多还是尽可能重，都可把每个箱子视为三种状态。那就是该箱子不选（状态为 0）？或是放上第一艘船（状态为 1）？还是放上第二艘船（状态为 2）？转化为求解问题解向量（x1, x2, , xn），xi0, 1, 2，0代表不选即既不上第一艘船也不上第二艘船，1 代表装上第一艘船，2 代表装上第二艘船。那这个解空间树就是一棵完全三叉树，采用深度优先的回溯算法可无遗漏地找到尽可能多或是尽可能重的最

11、优解，这样搜索一定可以找到最优解。4-3 参考解答：若字符 ah 出现的频率恰好是前 8 个 Fibonacci 数，它们的 Haffman 编码树如下图所示。0101hg0100111fe0d1bc0a将结果推广到 n 个字符频率恰好是前 n 个 Fibonacci 数，则相应的 Haffman 编码树和上图类似，树的深度为 n-1，第一第二个字符编码长度为 n-1，这可以根据 Haffman 树的构造和数学归纳法证明得到。第四章 贪心算法算法实现题：4-6 实现：最短服务时间优先。4-9 实现最远：优先。4-10 实现：每次覆盖尽可能多的点。4-11 实现从数的：到低位扫描，递减区间的首字

12、符优先考虑删除掉。4-14 实现：最大费用：每次选最大的 2 个元素合并最小费用：每次选最小的 k 个元素合并贪心的方法如下：保证每次选两堆最多的，合并直至只剩一堆为止，能获得最大得分；这个和 huffman 树构造是相同的，不再详述！保证每次选 k 堆最少的，合并直至只剩一堆为止，能获得最小得分。这个是多元 huffman 树的构造。要注意的是：在合并之前，若 n%(k-1)!=1，说明合并到最后一轮时，剩下不是 k 堆（而是比 k 堆少），这样算的并不是最小得分，而必须在合并之前添加若干个为 0 的虚拟堆，目的为凑成的堆数保证每次都能有 k 堆合并（包括最后一次）最后合并为 1 堆。因此，

13、在合并前作如下处理：/假设石头每堆个数放于 stone1stonen,且 stonen之后最多 k-1 个数组单元为可写：4-15 实现：若 a+b=n，则|a-b|越小，a*b 越大。贪心策略：因为因子互不相同，因此将 n 分成从 2 开始的连续自然数之和，若最后剩下一个数，将此数后项优先的方式下均匀地分给前面各项。while (n % (k - 1) != 1)n+;stonen=0;最后再补充第三版算法实现题的 3-2 和 4-11，这两题在第四版书中被删除了，这两题就是“最少找零钱”。3-2 实现（此题是第三版书的 3-2）：对比此题和 4-11 不同，4-11 的硬币面值是确定的 5

14、,10,20,50,100 和 200，可以用贪心算法解决。而此题！这里注意各个硬币的面值是输入的，于 T1:n中。n 种面值，找钱数 m。 cij：表示当使用面值 T1, , Ti这 i 种面值的硬币时，需要找回钱数 j 所使用的最少硬币个数，这里 1in,1jm。若找不出找钱方案， cij 。cij的递推表达式如下：cij mink ci 1 j k *Ti ，这里 k 表示最后一种币值 Ti的0k j / T i。初始条件：ci0 0, i 1 nc1j ( j mod T1) 0 j / T1( j mod T1) 0或者这样考虑也可以：设 cj（j=1m）表示用所有钱币 T1.n的找

15、钱 j 的最少钱币。对于任何 1in,1jm，若 j-Ti0，则 cj-Ti表示找钱 j-Ti的最优，再加上 1 张面值为 Ti的币值就可以找回钱数 j 了，且所用的钱为 cj-Ti+1。由此可知，cj min1 c j Tii 1 n, j 1 m1in c1 T1 11T1 14-11 实现（此题是第三版书的 4-11，此题贪心的简单，但“贪心选择性质”的证明较为复杂，仅看看，不要求掌握证明！）：对比此题和 3-2 不同，此题的硬币面值是确定的 5,10,20,50,100 和 200，可以用贪心算法解决。而 3-2 题需用动态规划来解决。找零的每步都选择最大面值的硬币，最终可以保证硬币总

16、个数最少。【因为有较多同学对找零问题的贪心算法正确性证明有疑问，因此现证明如下：】对特定面值的找零钱问题的贪心算法正确性证明，先来看以 1 分，5 分，1 角，2 角五分这 4 种币值的零钱最少面再写）：找零，而此题的 5,10,20,50,100 和 200 分也同理可证（后设面值存于 c1=1,c2=5,c3=10,c4=25，找钱后各种面值为 s1:4，使得：4min i14s.t. sici n, 且si为非负整数i1（1）最优子结构性质设 si,i=14 是上述找零问题的一个最优解，则对任意 1j4 且 sj0，取 ti=si, 1i4,ij；tj=sj-1。则 ti, 1i4 是如

17、下子问题的最优解。4min i14s.t. sici n c ji1（2）贪心选择性质此题贪心策略为优先选择尽可能的面值找零。则需证明对于任意一个值 n（n 为整数，以分为 ），都可以找到最佳找零方案包含小于 n 且最大的那种面值。假设，c1=1,c2=5,c3=10,c4=25，对于找零问题的任意一组最优解 si, 1i4，一定有：s14，s21，s32，s4可能任意。【反证】：事实上，若 s15，则可以用 1张 c2面值的去替换 5 张 c1面值的钱；若 s22，则可以用 1 张 c3面值的去替换 2 张 c2面值的钱；若 s33，则可以用 1 张 c4面值和 1 张 c2面值的去替换 3

18、 张 c3面值的钱。这些替换都导致 si ,1i4 不是最优解。另外，当 s3=2 时，一定有 s2=0，因如若不然，s21，由 2*c3+c2=c4可知，si ,1i4 不是最优解。因此，现在对找零总数 n（以分为，n 是整数）的各种情况：41）n25，由所有零钱总钱数为 n（即 sici n ），可知 s40。因如若不然，i133 sici n ，由前面分析可知，s1最大为 4，s2最大为 0，s3最大为 2， sici =i1i14*1+0*5+2*10，最大可能凑出 24，与 n25择最大币值的贪心策略；，假设不成立，因此 s40，满足优先选2）10n25，同理3）5n10，同理4）1n0，满足贪心策略；，s20，满足贪心策略；，s10，满足贪心策略；此题的 5 分,10 分,20 分,50 分,100 分和 200 分面值设置：n%5 = = 0 才可找，若 n%50不可找。c1=5,c2=10,c3=20,c4=50,c5=100,c6=200。最优子结构显然满足。与前面的分析和证明同理，最优解 s1:6，一定有 s11, s21, s32（若 s33，用 1 张 10 分的和 1 张 50 分的替换将产生更少的钱的）, s41, s51, s6可能任意。且当 s3=2 时，s2一定为 0