计算机算法分析—第五章作业

1、计算机算法分析计算机算法分析习题课习题课 第五章：第五章：3 、6、7、8 、 9 、11 、 12 P122-3 n3（0/1背包问题）如果将背包问题）如果将5.3节讨论的背包节讨论的背包 问题修改成问题修改成 n 极大化极大化 n 约束条件约束条件 n xi=0或或1 1in n这种背包问题称为这种背包问题称为0/1背包问题。它要求物品背包问题。它要求物品 或者整件装入背包或者整件不装入。求解此问或者整件装入背包或者整件不装入。求解此问 题的一种贪心策略是：按题的一种贪心策略是：按pi/wi的非增次序考虑的非增次序考虑 这些物品，只要正被考虑的物品能装的进就将这些物品，只要正被考虑的物品能

2、装的进就将 其装入背包。证明这种策略其装入背包。证明这种策略不一定不一定能得到最优能得到最优 解。解。 1 n ii p x 1 n ii w xM P122-3 q证明（反证法）： 设n = 3，M = 6， (p1, p2, p3) = (3, 4, 8)，(w1, w2, w3) = (1, 2, 5) 按照pi/wi 的非增序得到 ( p1/w1, p2/w2, p3/w3) = (3, 2,1.6)， 则其解为(1, 1, 0)，而事实上最优解是(1, 0, 1) 。 问题得证。 q若所装入的物品能装满背包时，为最优解 P122-3 0/1背包问 题可行解 集合 q结论：当按照pi

3、/wi的非增次序考虑物品存放 背包时，如果所装入的物品能装满背包时， 显然为最优解，否则未必是最优解. 背包问题 可行解集 合 装满时对 应的可行 解 P122-3 q附：0/1背包问题是一个NP完全问题，NP完 全问题是否存在多项式时间的求解算法目前 仍未可知，这也是计算机科学领域最著名的 开放问题“NP = P是否成立”（绝大多数人 相信NP = P不成立），因此，谁如果对0/1 背包问题给出一种正确的贪心算法，必然获 得图灵奖 P122- 6 n假定要将长为假定要将长为l1,l2,ln的的n个程序存入一盘磁个程序存入一盘磁 带，程序带，程序Ii被检索的频率是被检索的频率是fi。如果程序按

4、。如果程序按 i1,i2,in的次序存放，则期望检索时间（的次序存放，则期望检索时间（ERT） 是是: 1 ()/ jk j iii jk flf n 证明按证明按li的非降次序存放程序不一定得到最的非降次序存放程序不一定得到最 小的小的ERT。 n 证明按证明按fi的非增次序存放程序不一定得到最的非增次序存放程序不一定得到最 小的小的ERT。 n 证明按证明按fi/li的非增次序来存放程序时的非增次序来存放程序时ERT取取 最小值。最小值。 P122- 6 n问题实例:(l1, l2, l3) = (5, 6, 12)，(f1, f2, f3) = (0.2, 0.3, 0.5) nli的非

5、降次序： 1 = (1, 2, 3) nfi的非增次序： 2 = (3, 2, 1) nfi /li的非增次序的非增次序： 3 = (2, 3, 1) nERT( 1) = 50.2 + (5+6)0.3 + (5+6+12) 0.5 = 15.8 nERT( 2)=120.5+(12+6) 0.3+(12+6+5) 0.2=16 nERT( 3)=60.3 + (6+12)0.5 + (6+12+5) 0.2=15.4 P122 - 6 证明按证明按fi/li的非增次序来存放程序时的非增次序来存放程序时 ERT取最小值。取最小值。 n 假设假设i1,i2,in按照按照fi/li的非增次序存放

6、，即的非增次序存放，即 fi1/li1fi2/li2fin/lin，则得到，则得到 ERT=fi1li1+fi2(li1+li2)+fik(li1+li2+lik)+fin(l i1+li2+lin)/(fi1+.+fin) n假设该问题的一个最优解是按照假设该问题的一个最优解是按照j1,j2,jn的顺序的顺序 存放，并且其期望检索存放，并且其期望检索时间时间是是ERT，我们只需证，我们只需证 明明ERTERT，即可证明按照，即可证明按照fi/li的非增次序存放的非增次序存放 得到的是最优解。得到的是最优解。 n从前向后考察最优解序列：从前向后考察最优解序列：j1,j2,jn，若与，若与 i1

7、,i2,in相同，命题得证。相同，命题得证。 n否则，不妨设程序否则，不妨设程序jk是第一个与其相邻的程序是第一个与其相邻的程序jk+1 存在关系存在关系fjk/ljk0，既有，既有 ERT ERT，显然，显然ERT也是最优解。也是最优解。 n最优解中所有这样类似于反序对的程序互换位置，最优解中所有这样类似于反序对的程序互换位置， 每次得到的解不比原来的最优解差，所以最终变每次得到的解不比原来的最优解差，所以最终变 换后得到的解也是最优解，而最终的解恰是程序换后得到的解也是最优解，而最终的解恰是程序 按按fi/li的非增次序来存放得到的顺序。的非增次序来存放得到的顺序。 n命题得证。命题得证。

8、 P123-8 n 当当n=7，（，（p1 , p7）=(3,5,20,18,1,6,30) 和和(d1,d7)=(1,3,4,3,2,1,2)时，算法时，算法5.4所生所生 成的解是什么？成的解是什么？ n 证明即使作业有不同的处理时间定理证明即使作业有不同的处理时间定理5.5亦亦 真。这里，假定作业真。这里，假定作业i的效益的效益pi0，要用的处，要用的处 理时间理时间ti0，限期，限期diti. P123-8 n解：解：根据根据pi的非增排序得到（的非增排序得到（p7, p3, p4, p6, p2, p1, p5）=(30,20,18,6,5,3,1)，对应的期限，对应的期限 为为(2

9、,4,3,1,3,1,2)，按照算法，按照算法5.4生成的解为：生成的解为： nJ(1)=7(2), nJ(1)=7(2), J(2)=3(4)； nJ(1)=7(2), J(2)=4(3),J(3)=3(4)； 1.J(1)=6(1), J(2)=7(2),J(3)=4(3),J(4)=3(4)； P123-8 n 证明即使作业有不同的处理时间定理证明即使作业有不同的处理时间定理5.3亦真。这亦真。这 里，规定作业里，规定作业i的效益的效益pi0，要用的处理时间，要用的处理时间ti0，限，限 期期diti.(P106) n定理定理5.3:设设J是是K个作业的集合个作业的集合, =i1i2ik

10、是是J中作业中作业 的一种排序的一种排序,它使得它使得di1di2dik .J是一个可行解是一个可行解,当当 且仅当且仅当J中的作业可以按照中的作业可以按照 的次序又不违反任何一个的次序又不违反任何一个 期限的情况下来处理期限的情况下来处理. n证明思想：证明思想： q q 位置位置a,b的作业交换顺序的作业交换顺序 n作业作业ra和和rb仍然可以完成任务仍然可以完成任务 n作业作业ra和和rb之间的作业也能够完成任务之间的作业也能够完成任务 P123-8 P123-9 n 对于对于5.3节的作业排序问题证明：当且仅当节的作业排序问题证明：当且仅当 子集合子集合J中的作业可以按下述规则处理时它

11、表中的作业可以按下述规则处理时它表 示一个可行解；如果示一个可行解；如果J中的作业中的作业I还没分配处理还没分配处理 时间，则将它分配在时间片时间，则将它分配在时间片a-1，a处理，其处理，其 中中a是使得是使得1rdi的最大整数的最大整数r，且时间片，且时间片a-1， a是空的。是空的。 n 仿照例仿照例5.4的格式，在习题的格式，在习题8所提供的数所提供的数 据集上执行算法据集上执行算法5.5。 P123-9 n易证如果易证如果J中的作业能按上述规则处理，显然中的作业能按上述规则处理，显然J是可行是可行 解；解； n如果如果J是可行解，根据定理是可行解，根据定理5.3可知，可知，J中的作业

12、根据中的作业根据 时间期限的非降次序排列，得到时间期限的非降次序排列，得到i1i2ik in ，并且按，并且按 照这个顺序，可以处理照这个顺序，可以处理J中所有作业，而对这一序列中所有作业，而对这一序列 中的任意作业中的任意作业ik，如果它的时间期限是，如果它的时间期限是dk，且时间片，且时间片 dk-1,dk是空的，则分配之；若时间片是空的，则分配之；若时间片dk-1，dk非非 空，则向前找最大的非空空，则向前找最大的非空r-1,r时间片，时间片，1rdk。 。因 因 为为J是可行解，所以一定可以找到如此时间片。故命是可行解，所以一定可以找到如此时间片。故命 题得证。题得证。 nn=7 (p

13、1, p7)=(3,5,20,18,1,6,30) (d1,d7)=(1,3,4,3,2,1,2) n(p7, p3, p4, p6, p2, p1, p5) =(30,20,18,6,5,3,1)， 对应的期限为对应的期限为(2,4,3,1,3,1,2) b=min n,maxd(i) =min7,4 =4 F(0)F(1)F(2)F(3)F(4) 01234 -1 0 -1 1 -1 2 -1 3 -1 4 F(0)F(1)F(2)F(3)F(4) 01134 -1 0 -2 1 1 2 -1 3 -1 4 空空 7 F(0)F(1)F(2)F(3)F(4) 01133 7,3 -1 0

14、-2 1 1 2 -2 3 3 4 (p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)，对应的期限为，对应的期限为(2,4,3,1,3,1,2) (p7, p3, p4, p6, p2, p1, p5)=(30,20,18,6,5,3,1)，对应的期限为，对应的期限为(2,4,3,1,3,1,2) F(0)F(1)F(2)F(3)F(4) 01113 7,3,4 -1 0 -4 1 1 2 1 3 3 4 F(0)F(1)F(2)F(3)F(4) 00113 7,3,4,6 1 0 -5 1 1 2 1 3 3 4 F(0)F(1)F(2) F(3)

15、F(4) 00113 7,3,4,6 1 0 -5 1 1 2 1 3 1 4 P123-11 n 证明如果一棵树的所有内部节点的度都为证明如果一棵树的所有内部节点的度都为k， 则外部节点数则外部节点数n满足满足n mod (k-1)=1. n 证明对于满足证明对于满足 n mod (k-1)=1的正整数的正整数n， 存在一棵具有存在一棵具有n个外部节点的个外部节点的k元树元树T(在一棵在一棵k 元树中，每个节点的度至多为元树中，每个节点的度至多为k)。进而证明。进而证明T 中所有内部节点的度为中所有内部节点的度为k. P123-11 证明如果一棵树的所有内部节点的度证明如果一棵树的所有内部节

16、点的度 都为都为k，则外部节点数，则外部节点数n满足满足n mod (k-1)=1. n证明：证明： 设这棵树内部节点的个数是设这棵树内部节点的个数是i，外部，外部 结点的个数是结点的个数是n，边的条数是，边的条数是e，则有，则有 ne=i+n-1 nik=e n ik=i+n-1 n (k-1)i=n-1 n n mod (k-1)=1 P123-11 证明对于满足证明对于满足 n mod (k-1)=1的正整数的正整数n， 存在一棵具有存在一棵具有n个外部节点的个外部节点的k元树元树T(在一棵在一棵k元树元树 中，每个节点的度至多为中，每个节点的度至多为k)。进而证明。进而证明T中所有内中

17、所有内 部节点的度为部节点的度为k. n 利用数学归纳法利用数学归纳法(m表示外部结点数目表示外部结点数目)。 n当当m =k时，存在外部结点数目为时，存在外部结点数目为k的的k元树元树T， 并且并且T中内部结点的度为中内部结点的度为k； 例如：例如： m=3 3mod(3-1)=1 n假设当假设当 m n，且满足，且满足m mod (k-1)=1时，存时，存 在一棵具有在一棵具有m个外部结点的个外部结点的k元树元树T，且所有内，且所有内 部结点的度为部结点的度为k； n我们将外部结点数为我们将外部结点数为m的符合上述性质的树的符合上述性质的树T 中某个外部结点用内部结点中某个外部结点用内部结

18、点 a替代，且结点替代，且结点a 生出生出k个外部结点个外部结点. a n易知新生成的树易知新生成的树T中外部结点的数目为中外部结点的数目为n= m - 1+k= m +(k-1)，因为，因为 m mod (k-1)=1，所以，所以n 为满足为满足n mod (k-1)=1，且比，且比m大的最小整数，大的最小整数， 而树而树T每个内结点的度为每个内结点的度为k，所以，所以n= m +(k-1) 时，存在符合上述性质的树。故命题得证。时，存在符合上述性质的树。故命题得证。 a P123-12 n 证明如果证明如果n mod (k-1)=1，则在定理，则在定理5.4后后 面所描述的贪心规则对于所有

19、的（面所描述的贪心规则对于所有的（q1,q2,qn） 生成一棵最优的生成一棵最优的k元归并树。元归并树。 n 当（当（q1,q2,q11）= （3,7,8,9,15,16,18,20,23,25,28）时，画出使）时，画出使 用这一规则所得到的最优用这一规则所得到的最优3元归并树。元归并树。 P123-12 证明如果证明如果n mod (k-1)=1，则在定理，则在定理3.6 后面所描述的贪心规则对于所有的（后面所描述的贪心规则对于所有的（q1,q2,qn）生）生 成一棵最优的成一棵最优的k元归并树。元归并树。 n通过数学归纳法证明：通过数学归纳法证明： n对于对于n=1，返回一棵没有内部结点

20、的树且这棵树，返回一棵没有内部结点的树且这棵树 显然是最优的。显然是最优的。 n假定该算法对于（假定该算法对于（q1,q2,qm），其中），其中m=(k- 1)s+1 (s0)，都生成一棵最优树，都生成一棵最优树， n则只需证明对于则只需证明对于(q1,q2,qn)，其中，其中n=(k- 1)(s+1)+1，也能生成最优树即可。，也能生成最优树即可。 n不失一般性，假定不失一般性，假定q1q2qn，且，且q1,q2,qk 是算法所找到的是算法所找到的k棵树的棵树的WEIGHT信息段的值。信息段的值。 于是于是q1,q2,qk可生成子树可生成子树T，设，设T是一棵对于是一棵对于 （q1,q2,qn）的最优）的最优k元归并树。设元归并树。设P是距离是距离 根最远的一个内部结点。如果根最远的一个内部结点。如果P的的k个儿子不是