一次输入一个量。如果这个输入和前面输入产生的在这种度量意义下的部分最优解加在一起产生一个可行解，将其加入形成新的在这种度量意义下的部分最优解；若不能构成一个可行解，则去掉该输入；重复此过程直到将输入枚举完成。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心方法。
贪心方法的SPARKS语言描述的抽象化控制为： Procedure GREEDY(A,n) soltion??
for i?1 to n do x?SELECT(A)
if FEASIBLE(soltion,x)
then soltion?UNION(soltion,x) endif repeat
return(soltion) end GREEDY
24．① 求以下情况背包问题的最优解，n=7，m=15，=(10,5,15,7,6,18,3)（p1,.....p7）（w1,.....w7）和=(2,3,5,7,1,4,1)。
② 将以上数据情况的背包问题记为I。设FG(I)是物品按pi的非增次序输入时由GREEDY-KNAPSACK所生成的解，FO(I)是一个最优解。问FO(I)/ FG(I)是多少?
③ 当物品按wi的非降次序输入时，重复②的讨论。 解：① 按照pi/wi的非增序可得
(p5/w5，p1/w1，p6/w6，p3/w3，p7/w7，p2/w2，p4/w4) = (6,5,9/2,3,3,5/3,1)
W的次序为(1,2,4,5,1,3,7),解为(1,1,1,1,1,2/3,0) 所以最优解为：（1,2/3,1,0,1,1,1）
FO(I)=166/3
② 按照Pi的非增次序输入时得到
(p6,p3,p1,p4,p5,p2,p7)= (18,15,10,7,6,5,3)，
对应的(w6,w3,w1,w4,w5,w2,w7)= (4,5,2,7,1,3,1) 解为(1,1,1,4/7,0,0,0)
所以FG(I)的解为（1,0,1,4/7,0,1,0） FG(I)=47，所以FO(I)/ FG(I)=166/141.
③ 按照wi的非降次序输入时得到
(w5,w7,w1,w2,w6,w3,w4)=(1,1,2,3,4,5,7) 相应的(p5,p7,p1,p2,p6,p3,p4)=(6,3,10,5,18,15,7) 解为(1,1,1,1,1,4/5,0)
则FW(I)的解为（1,1,4/5,0,1,1,1） FW(I)=54，所以FO(I)/ FW(I)=83/81.
25．（0/1背包问题）如果将5.3节讨论的背包问题修改成
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)，问题得证。
26．假定要将长为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，则得到
122 ERT=[fili+fi(li+li)+?+fi(li+li+?+ li]/?fi
11212n12nni?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的非增次序来存放得到的顺序。命题得证。 27.假定要把长为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，所以得证。
28.①当n=7，=(3,5,20,18,1,6,30) 和（p1,.....p7）（d1,.....d7）=(1,3,4,3,2,1,2)时，算法5.4所生成的解是什么？
② 证明即使作业有不同的处理时间定理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的次序处理而不违
相关推荐：
loading