资源描述：
《算法分析作业-第5章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、算法分析作业第5章贪心法最优化问题约束条件目标函数最优量度标准(贪心规则、贪心选择性质)试探、证明贪心法不一定能求得最优值，大多数情况得到较优值；2、3、6、7、8、9、11、12P121-2．求以下情况背包问题的最优解，n=7，m=15，（p1,…,p7）=(10,5,15,7,6,18,3)和(w1,…,w7)=(2,3,5,7,1,4,1)。将以上数据情况的背包问题记为I。设FG(I)是物品按pi的非增次序输入时由GREEDY-KNAPSACK所生成的解，FO(I)是一个最优解。问FO(I)/FG(I)是多少?当物品按wi的非降次序输入时，重复②的讨论。求背包问题
2、的最优解n=7，m=15根据贪心（x5,x1,x6,x3,x7,x2,x4）=（1,1,1,1,1,2/3,0）即(x1,x2,x3,x4,x5,x6,x7)=(1,2/3,1,0,1,1,1)FO(I)=166/3。i1234567p1051576183w2357141p/w55/33169/23x12/31111按照Pi的非增次序：n=7，m=15根据贪心（x6,x3,x1,x4,x5,x2,x7）=（1,1,1,4/7,0,0,0）即FG(I)的解为(0,1,0,1,1,0,4/7)，FG(I)=47FO(I)/FG(I)=166/141i1234567p1051
3、576183w2357141x117/41物品按wi的非降次序：n=7，m=15根据贪心（x5,x7,x1,x2,x6,x3,x4）=（1,1,1,1,1,4/5,0）即FG(I)的解为(1,1,4/5,0,1,1,1)，FG(I)=54FO(I)/FG(I)=166/162=83/81i1234567p1051576183w2357141x114/5111P122-3．（0/1背包问题）如果将5.3节讨论的背包问题修改成极大化约束条件xi=0或11≤i≤n这种背包问题称为0/1背包问题。它要求物品或者整件装入背包或者整件不装入。求解此问题的一种贪心策略是：按pi/wi
4、的非增次序考虑这些物品，只要正被考虑的物品能装的进就将其装入背包。证明这种策略不一定能得到最优解。P122-3证明：按照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-6．假定要将长为l1,l2,…,ln的n个程序存入一盘磁带，程序i被检索
5、的频率是fi。如果程序按i1,i2,…,in的次序存放，则期望检索时间（ERT）是:①证明按li的非降次序存放程序不一定得到最小的ERT。②证明按fi的非增次序存放程序不一定得到最小的ERT。③证明按fi/li的非增次序来存放程序时ERT取最小值。P122-6．①证明按li的非降次序存放程序不一定得到最小的ERT。I:(l1,l2)=(10,12)(f1,f2)=(0.4,0.6)ERT(I)=10*0.4+(10+12)*0.6=17.2ERT(I’)=12*0.6+(10+12)*0.4=16P122-6．②证明按fi的非增次序存放程序不一定得到最小的ERT。I:(
6、l1,l2)=(2,1)(f1,f2)=(0.6,0.4)ERT(I)=2*0.6+(2+1)*0.4=2.4ERT(I’)=1*0.4+(1+2)*0.6=2.2P122-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的顺序存放，并且其期
7、望检索时间是ERT’，我们只需证明ERT≤ERT’，即可证明按照fi/li的非增次序存放得到的是最优解。从前向后考察最优解序列：j1,j2,…,jn，若与i1,i2,…,in相同，命题得证。否则，不妨设程序jk是第一个与其相邻的程序jk+1存在关系fjk/ljk
