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

计算机算法分析—习题课第五章：3、6、7、8、9、11、12P122-33．（0/1背包问题）如果将5.3节讨论的背包问题修改成极大化 约束条件

xi=0或11≤i≤n这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按pi/wi的非增次序考虑这些物品，只要正被考虑的物品能装的进就将其装入背包。证明这种策略不一定能得到最优解。P122-3证明（反证法）： 设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)。问题得证。若所装入的物品能装满背包时，为最优解P122-30/1背包问题可行解集合结论：当按照pi/wi的非增次序考虑物品存放背包时，如果所装入的物品能装满背包时，显然为最优解，否则未必是最优解.背包问题可行解集合装满时对应的可行解P122-3附：0/1背包问题是一个NP完全问题，NP完全问题是否存在多项式时间的求解算法目前仍未可知，这也是计算机科学领域最著名的开放问题“NP=P是否成立”（绝大多数人相信NP=P不成立），因此，谁如果对0/1背包问题给出一种正确的贪心算法，必然获得图灵奖P122-6．假定要将长为l1,l2,…,ln的n个程序存入一盘磁带，程序Ii被检索的频率是fi。如果程序按i1,i2,…,in的次序存放，则期望检索时间（ERT）是:①证明按li的非降次序存放程序不一定得到最小的ERT。②证明按fi的非增次序存放程序不一定得到最小的ERT。③证明按fi/li的非增次序来存放程序时ERT取最小值。P122-6．问题实例:(l1,l2,l3)=(5,6,12)，(f1,f2,f3)=(0.2,0.3,0.5)li的非降次序：1=(1,2,3)

fi的非增次序：2

=(3,2,1)

fi/li的非增次序：3

=(2,3,1)ERT(1)=5×0.2+(5+6)×0.3+(5+6+12)×0.5=15.8ERT(2)=12×0.5+(12+6)×0.3+(12+6+5)×0.2=16ERT(3)=6×0.3+(6+12)×0.5+(6+12+5)×0.2=15.4P122-6．③证明按fi/li的非增次序来存放程序时ERT取最小值。假设i1,i2,…,in按照fi/li的非增次序存放，即fi1/li1≥fi2/li2≥…≥fin/lin，则得到ERT=[fi1li1+fi2(li1+li2)+…+fik(li1+li2+…+lik)+…+fin(li1+li2+…+lin)]/(fi1+..+fin)假设该问题的一个最优解是按照j1,j2,…,jn的顺序存放，并且其期望检索时间是ERT’，我们只需证明ERT≤ERT’，即可证明按照fi/li的非增次序存放得到的是最优解。从前向后考察最优解序列：j1,j2,…,jn，若与i1,i2,…,in相同，命题得证。否则，不妨设程序jk是第一个与其相邻的程序jk+1存在关系fjk/ljk<fjk+1/ljk+1，交换程序jk和程序jk+1，得到的期望检索时间记为ERT’’。ERT’-ERT’’=(fjk+1ljk–fjkljk+1)/(fi1+..+fin)>0，既有ERT’’≤ERT’，显然ERT’’也是最优解。最优解中所有这样类似于反序对的程序互换位置，每次得到的解不比原来的最优解差，所以最终变换后得到的解也是最优解，而最终的解恰是程序按fi/li的非增次序来存放得到的顺序。命题得证。P123-8①当n=7，（p1,…,p7）=(3,5,20,18,1,6,30)和(d1,…,d7)=(1,3,4,3,2,1,2)时，算法5.4所生成的解是什么？②证明即使作业有不同的处理时间定理5.5亦真。这里，假定作业i的效益pi>0，要用的处理时间ti>0，限期di≥ti.P123-8解：①根据pi的非增排序得到（p7,p3,p4,p6,p2,p1,p5）=(30,20,18,6,5,3,1)，对应的期限为(2,4,3,1,3,1,2)，按照算法5.4生成的解为：

J(1)=7(2),J(1)=7(2),J(2)=3(4)；J(1)=7(2),J(2)=4(3),J(3)=3(4)；

J(1)=6(1),J(2)=7(2),J(3)=4(3),J(4)=3(4)；P123-8②证明即使作业有不同的处理时间定理5.3亦真。这里，规定作业i的效益pi>0，要用的处理时间ti>0，限期di≥ti.(P106)定理5.3:设J是K个作业的集合,=i1i2…ik是J中作业的一种排序,它使得di1≤di2≤…≤dik.J是一个可行解,当且仅当J中的作业可以按照的次序又不违反任何一个期限的情况下来处理.证明思想：←→位置a,b的作业交换顺序作业ra和rb仍然可以完成任务作业ra和rb之间的作业也能够完成任务P123-8P123-9①对于5.3节的作业排序问题证明：当且仅当子集合J中的作业可以按下述规则处理时它表示一个可行解；如果J中的作业I还没分配处理时间，则将它分配在时间片[a-1，a]处理，其中a是使得1≤r≤di的最大整数r，且时间片[a-1，a]是空的。②仿照例5.4的格式，在习题8①所提供的数据集上执行算法5.5。P123-9易证如果J中的作业能按上述规则处理，显然J是可行解；如果J是可行解，根据定理5.3可知，J中的作业根据时间期限的非降次序排列，得到i1i2…ik…in，并且按照这个顺序，可以处理J中所有作业，而对这一序列中的任意作业ik，如果它的时间期限是dk，且时间片[dk-1,dk]是空的，则分配之；若时间片[dk-1，dk]非空，则向前找最大的非空[r-1,r]时间片，1≤r≤dk。因为J是可行解，所以一定可以找到如此时间片。故命题得证。n=7(p1,…,p7)=(3,5,20,18,1,6,30)(d1,…,d7)=(1,3,4,3,2,1,2)(p7,p3,p4,p6,p2,p1,p5)=(30,20,18,6,5,3,1)，对应的期限为(2,4,3,1,3,1,2)b=min{n,max{d(i)}}=min{7,4}=4F(0)F(1)F(2)F(3)F(4)01234-10-11-12-13-14F(0)F(1)F(2)F(3)F(4)01134-10-2112-13-14空{7}F(0)F(1)F(2)F(3)F(4)01133{7,3}-10-2112-2334(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}-10-41121334F(0)F(1)F(2)F(3)F(4)00113{7,3,4,6}10-51121334F(0)F(1)F(2)F(3)F(4)00113{7,3,4,6}10-51121314P123-11①证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足nmod(k-1)=1.②证明对于满足nmod(k-1)=1的正整数n，存在一棵具有n个外部节点的k元树T(在一棵k元树中，每个节点的度至多为k)。进而证明T中所有内部节点的度为k.P123-11①证明如果一棵树的所有内部节点的度都为k，则外部节点数n满足nmod(k-1)=1.证明：①设这棵树内部节点的个数是i，外部结点的个数是n，边的条数是e，则有e=i+n-1ik=eik=i+n-1(k-1)i=n-1nmod(k-1)=1P123-11②证明对于满足nmod(k-1)=1的正整数n，存在一棵具有n个外部节点的k元树T(在一棵k元树中，每个节点的度至多为k)。进而证明T中所有内部节点的度为k.

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

a替代，且结点a生出k个外部结点.…a易知新生成的树T’中外部结点的数目为n=m-1+k=m+(k-1)，因为mmod(k-1)=1，所以n为满足nmod(k-1)=1，且比m大的最小整数，而树T’每个内结点的度为k，所以n=m+(k-1)时，存在符合上述性质的树。故命题得证。…aP123-12①证明如果nmod(k-1)=1，则在定理5.4后面所描述的贪心规则对于所有的（q1,q2,…,qn）生成一棵最优的k元归并树。②当（q1,q2,…,q11）=（3,7,8,9,15,16,18,20,23,25,28）时，画出使用这一规则所得到的最优3元归并树。P123-12①证明如果nmod(k-1)=1，则在定理3.6后面所描述的贪心规则对于所有的（q1,q2,…,qn）生成一棵最优的k元归并树。通过数学归纳法证明：对于n=1，返回一棵没有内部结点的树且这棵树显然是最优的。假定该算法对于（q1,q2,…,qm），其中m=(k-1)s+1(s≥0)，都生成一棵最优树，则只需证明对于(q1,q2,…,qn)，其中n=(k-1)(s+1)+1，也能生成最优树即可。不失一般性，假定q1≤q2≤…≤qn，且q1,q2,…,qk是算法所找到的k棵树的WEIGHT信息段的值。于是q1,q2,…,qk可生成子树T，设T’是一棵对于（q1,q2,…,qn）的最优k元归并树。设P是距离根最远的一个内部结点。如果P的k个儿子不是q1,q2,…,qk，则可以用q1,q2,…,qk和P现在的儿子进行交换，这样不增加T’的加权外部路径长度。因此T也是一棵最优归并树中的子树。于是在T’中如果用其权为q1+q2+…+qk的一个外部结点来代换T，则所生成的树T’’是关于(T,qk+1,…,qn)的一棵最优归并树。由归纳假设，在使用其权为q1+q2+…+qk的那个外部结点代换了T以后，过程TREE转化成去求取一棵关于(T,qk+1,…,qn)的最优归并树。因此TREE生成一棵关于(q1,q2,…,qn)的最优归并树。（q1,q2,…,q11）=（3,7,8,9,15,16,18,20,23,25,28）78323252891516182078323