算法设计与分析（王佳）05动态规划.pptVIP

2) 时间复杂度 由Si-1生成Si的时间为： ，0≤i≤n-1 故，DKNAP计算所有的Si所需的时间为： 进一步考察： 若每件物品的重量wi和效益值pi均为整数，则Si中每个序偶(P,W)的P值和W值也是整数，且有 ，W≤M 又，在任一Si中，所有序偶具有互异P值和W值，故有 且 至少有一个（0,0） 故，在所有wj和pj均为整数的情况下，DKNAP的时间和空间复杂度将为： 5. 序偶集合的一种启发式生成策略 在由S0生成Sn-1的过程中，有些序偶无论如何也不会导致问题的最优解，这些序偶最终也不会出现在任何最优决策序列中，故可以及时的舍去，以进一步降低计算量。原理如下： 设L是最优解的估计值，但有fn(M)≥L 设PLEFT(i)= 即i+1至n件物品的效益值之和 若正在生成的序偶(P,W)有P＋PLEFT(i)＜L，则(P,W)将不计入Si中。 L的选择： ① 取Si的最末序偶(P,W)的P作为L，P≤fn(M) ② 将某些剩余物品的p值＋P作为L 例7.15 0/1背包问题 n=6,(p1,p2,p3,p4,p5,p6)=(w1,w2,w3,w4,w5,w6)=(100,50,20,10,7,3),M=165 不使用启发方法的序偶集 S0={0} S1={0,100} S2={0,50,100,150} S3={0,20,50,70,100,120,150} S4={0,10,20,30,50,60,70,80,100,110,120,130,150，160} S5={0,7,10,17,20,27,30,37,50,57,60,67,70,77,80,87,100,107,110,117,120,127,130,137,150,157,160} 则，f6(165)=163 注：每对序偶(P,W)仅用单一量P（或W）表示 启发式规则求解 分析：将物品1,2,4,6装入背包，将占用163的重量并产生163的效益。 故，取期望值L＝163. 按照启发式生成规则，从Si中删除所有P＋PLEFT(i)＜L的序偶，则有 PLEFT(0)=p1+p2+p3+p4+p5+p6=190 S0={0} ={100} PLEFT(1)=p2+p3+p4+p5+p6=90 S1={100} ={150} PLEFT(2)=p3+p4+p5+p6=40 S2={150} =? PLEFT(3)=p4+p5+p6=20 (w3=20) S3={150} ={160} PLEFT(4)=p5+p6=10 S4={160} = ? PLEFT(5)=p6=3 (w5=7) S5={160} PLEFT(6)=0 f6(165)=160+3 ＝ 163 7.8 流水作业问题 n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。 流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 分析： 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 设全部作业的集合为N={1，2，…，n}。S是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。 最优子结构性质 设π是所给n个流水作业的一个最优调度，它所需的加工时间为 aπ(1)+T’。其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，…，π(n)所需的