《计算机算法基础》第三版 - 课后习题答案

n 极大化

?px

ii1n 约束条件 ?wixi?M xi=0或1 1≤i≤n

1这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是:按pi/wi的非增次序考虑这些物品,只要正被考虑的物品能装进的就将其装入背包。证明这种策略不一定能得到最优解。

证明:当按照pi/wi的非增次序考虑物品存放背包时,如果所装入的物品恰能装满背包时,易证为最优解,否则未必是最优解。

可举例如下:设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),问题得证。

5.6.假定要将长为l1,l2,?, ln的n个程序存入一盘磁带,程序i被检索的频率是fi。如果程序按i1,i2,?, in的次序存放,则期望检索时间(ERT)是

njnik[?(fijj?1?lk?1)]/?fii?1

① 证明按li的非降次序存放程序不一定得到最小的ERT。 ② 证明按fi的非增次序存放程序不一定得到最小的ERT。 ③ 证明按fi/li的非增次序来存放程序时ERT取最小值。 证明:只需证明结论③是正确的即可,现证明如下: 假设li,li12,?, linnn按照fi/li的非增次序存放,即

fi1/li≥fi/li≥?≥fi/li,则得到

122n ERT=[fili+fi(li+li)+?+fi(li+li+?+ li]/?fi

11212n12ni?1假设该问题的一个最优解是按照j1,j2,?, jn的顺序存放,并且其期望检索式件是ERT?,我们只需证明ERT≤ERT?,即可证明按照fi/li的非增次序存

放得到的是最优解。易知

ERT?=[fj1lj1+fj2(lj+lj)+?+fj(lj+lj+?+ lj)]/?fi

12n12nni?1从前向后考察最优解中的程序,不妨设程序jk是第一个与其相邻的程序jk?1存在关系fj/lj≤fj/lj,则交换程序jk和程序jk?1,得到的期望检索时间

kkk?1k?1记为ERT??

ERT??-ERT?=fjkljk?1-fjk?1ljk≤0

ERT?? ≤ERT?

显然ERT??也是最优解,将原来的最优解中所有这样类似于反序对的程序互换位置,得到的解不比原来的最优解差,所以最终变换后得到的解也是最优解,而最终的解恰是程序按fi/li的非增次序来存放得到的顺序。命题得证。 5.7.假定要把长为l1,l2,?, ln的n个程序分布到两盘磁带T1和T2上,并且希望按照使最大检索时间取最小值的方式存放,即,如果存放在T1和T2上的程序集合分别是A和B,那么就希望所选择的A和B使得max{?i?Ali,?i?Bli}取最小值。一种得到A和B的贪心方法如下:开始将A和B都初始化为空,然后一次考虑一个程序,如果?i?Ali=min{?i?Ali,?i?Bli},则将当前正在考虑的那个程序分配给A,否则分配给B。证明无论是按l1≤l2≤?≤ln或是按l1≥l2≥?≥ln的次序来考虑程序,这种方法都不能产生最优解。

证明:按照l1≤l2≤?≤ln存放不会得到最优解,举例如下:

3个程序(a,b,c)长度分别为(1,2,3),根据题中的贪心算法,产生的解是A={a,c}B={b},则max{?i?Ali,?i?Bli}=4,而事实上,最优解应为3,所以得证.

按照l1≥l2≥?≥ln的次序存放也不会得到最优解,举例如下:

5个程序(a,b,c,d,e)长度分别为(10,9,8,6,4)根据题中的贪心算法,产生的解是A={a,d,e}B={b,c},则max{?i?Ali,?i?Bli}=20,而事实上,最优解应为19,所以得证。

(p1,.....p7)(d1,.....d7)5.8.①当n=7,=(3,5,20,18,1,6,30) 和=(1,3,4,3,2,1,2)

时,算法5.5所生成的解是什么?

② 证明即使作业有不同的处理时间定理5.3亦真。这里,假定作业I的效益

pi>0,要用的处理时间ti>0,限期di≥ti.

解:①根据

pi的

(p7,p3,p4,p6,p2,p1,p5)=(30,20,18,6,5,3,1),对应的期限为(2,4,3,1,3,1,2),按照算法5.4生成的解为:

a.J(1)=7

b.J(1)=7,J(2)=3

c.J(1)=7,J(2)=4,J(3)=3

d.J(1)=6, J(2)=7,J(3)=4,J(4)=3;

②证明:显然即使ti>0(di≥ti),如果J中的作业可以按照?的次序而又不

k违反任何一个期限来处理,即对?次序中的任一个作业k,应满足dk ≥?tj,

j?1则J就是一个可行解。

下面证明如果J是可行解,则使得J中的作业可以按照di,di,?, di排列

12n的序列?处理而又不违反任何一个期限。

k因为J是可行解,则必存在??=r1r2?rn,使得对任意的rk,都有dk≥?tj,

j?1我们设?是按照di≤di≤,?,≤di排列的作业序列。假设????,那么令a是使

12nra?ia的最小下标,设rb=ia,显然b>a,在??中将ra与rb相交换,因为dr≤dr,

ba显然ra和rb可以按期完成作业。

还要证明ra和rb之间的作业也能按期完成。因为dr≤dr,而显然二者之间

bab的所有作业rt,都有dr>dr,又由于?是可行解,所以?tk≤dr≤dr。所以作

tbbtk?1业ra和rb交换后,所有作业可依新产生的排列???==s1s2?sn的次序处理而不违反任何一个期限,连续使用这种方法,??就可转换成?且不违反任何一个期限,定理得证。

5.10① 已知n-1个元素已按min-堆的结构形式存放在A(1),?,A(n-1)。现要将另一存放在A(n)的元素和A(1:n-1)中元素一起构成一个具有n个元素的min-堆。对此写一个计算时间为O(logn)的算法。

② 在A(1:n)中存放着一个min-堆,写一个从堆顶A(1)删去最小元素后将

其余元素调整成min-堆的算法,要求这新的堆存放在A(1:n-1)中,且算法时间为O(logn).

③ 利用②所写出的算法,写一个对n个元素按非增次序分类的堆分类算法。分析这个算法的计算复杂度。

解:① procedure INSERT(A,n) integer i, j, k

j←n ; i←?n/2? while i≥1 and A[i]>A[j] do k←A[j];

A[j]←A[i]; A[i]←k

j←i ;

i←?i/2?

repeat end INSERT

② procedure RESTORE(A,l,n) integer i, j, k x←A[n];

A[n]←A[l]

i←1 j←2*i

while j≤n-1 do

if (j< n-1) and (A[j]> A[j+1])

then j←j+1 endif

if (x>A[j])

then A[i]←A[j]; i←j;j←2*i else i←n endif repeat end RESTORE

③ procedure HEAPSORT(A,n) integer i, k

for i=?n/2? to 1 step –1 do RESTORE(A, i, n) repeat

for i=n to 2 step –1 do

k←A[1]; A[1]←A[i]; A[i]←k RESTORE(A, 1, i-1) repeat

联系客服:779662525#qq.com(#替换为@)