算法分析与设计第六章3(01背包问题).ppt

《算法分析与设计第六章3(01背包问题).ppt》由会员分享，可在线阅读，更多相关《算法分析与设计第六章3(01背包问题).ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 动态规划动态规划2008-09-01版权所有：杨波，武汉科技大学理学院问题描述 1)KNAP(1,j,X)目标函数：约束条件：0/1背包问题：KNAP(1,n,M)最优性原理对于0/1背包问题成立 求解策略：向后处理法6.5 0/1背包问题背包问题2008-09-01版权所有：杨波，武汉科技大学理学院2)向后递推关系式 记fj(X)是KNAP(1,j,X)的最优解，则fn(M)有 fn(M)=maxfn-1(M),fn-1(M-wn)+pn 对于任意的fi(X)，i0,有 fi(X)=maxfi-1(X),fi-1(X-wi)+pi 递推过程：初始值 0 X0 f0(X)=X0

2、求出fi在所有可能的X取值情况下的值。fn(M)=KNAP(1,n,M)2008-09-01版权所有：杨波，武汉科技大学理学院例1 背包问题 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6递推计算过程第1个物品无法放入第1个物品可放入第1个物品无法放入第1个物品可放入，第2个物品无法放入第1个物品或第2个物品可放入第1个物品和第2个物品可放入2008-09-01版权所有：杨波，武汉科技大学理学院例1 背包问题 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6递推计算过程解向量的推导（最优的决策序列）f3(M)

3、=6x3=1f3(M)-p3=1f2(X)=1f1(X)=1x2=0 x1=1KNAP(1,3,6)=6X=(1,0,1)2008-09-01版权所有：杨波，武汉科技大学理学院f1,f2,f3计算过程的图解计算过程的图解(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 1234567012f0(x)=0i:fi-1(x-wi)+pii=0:函数不存在1234567012i1:f0(x-w1)+p11234567012f1(x)1234567012i2:f1(x-w2)+p23wwww12345670123wf2(x)fi-1(X-wi)+pi曲线的构造：将fi

4、-1(X)的曲线在X轴上右移wi个单位，然后上 移pi个单位而得到；fi(X)曲线的构造：由fi-1(X)和fi-1(X-wi)+pi的曲线按X相同时f取大值的规 则归并而成2008-09-01版权所有：杨波，武汉科技大学理学院12345670678w1234589i3:f2(x-w3)+p312345670678w1234589f3(x)101234567012i2:f1(x-w2)+p23w12345670123wf2(x)2008-09-01版权所有：杨波，武汉科技大学理学院1234567012i2:f1(x-w2)+p23wp12345670123wf2(x)p12345670678w

5、1234589i3:f2(x-w3)+p3p12345670678w1234589f3(x)10p(P,W)(0,0)(1,2)(2,3)(3,5)(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)(Pj,Wj):Pj=fi(Wj)2008-09-01版权所有：杨波，武汉科技大学理学院1234567012i2:f1(x-w2)+p23wp12345670123wf2(x)p12345670678w1234589i3:f2(x-w3)+p3p12345670678w1234589f3(x)10p(P,W)(0,0)(1,2)(2,3)(3,5)(5,4)(6,6)(7,7

6、)(8,9)(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)(5,4)+S2S3?2008-09-01版权所有：杨波，武汉科技大学理学院1234567012i2:f1(x-w2)+p23wp12345670123wf2(x)p12345670678w1234589i3:f2(x-w3)+p3p12345670678w1234589f3(x)10p(P,W)(0,0)(1,2)(2,3)(3,5)(5,4)(6,6)(7,7)(8,9)(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)S2S3?(0,0)(1,2)(2,3)(6,6)(7,7)(

7、8,9)(5,4)(3,5)支配规则：如果Si-1和 之一有序偶(Pj,Wj)，另一有(Pk,Wk)，且有 WjWk，PjPk，则序偶(Pj,Wj)将被舍弃。（即取最大值规则）。2008-09-01版权所有：杨波，武汉科技大学理学院 记 fi的序偶集合为 Si=(Pj,Wj)|Wj是fi曲线中使得fi产生一次跳跃的X值，0jr 即Pj=fi(Wj)，r是跳跃点个数 (P0,W0)=(0,0)若共有r个阶跃值，则分别对应r个(Pj,Wj)序偶，1jr 若WjWj+1,则PjPj+1，0jr 若WjXWj+1，fi(X)=fi(Wj)若XWr，fi(X)=fi(Wr)序偶表示序偶表示2008-09

8、-01版权所有：杨波，武汉科技大学理学院 Si的构造 记 是fi-1(X-wi)+pi的所有序偶的集合，则 其中，Si-1是fi-1的所有序偶的集合 Si的构造：由Si-1和 按照支配规则合并而成。支配规则：如果Si-1和 之一有序偶(Pj,Wj),另一有(Pk,Wk)，且有 WjWk,Pj Pk，则序偶(Pj,Wj)将被舍弃。（即取最大值规则）。注：Si中的序偶是背包问题KNAP(1,i,X)在X各种 取值下子问题的最优解2008-09-01版权所有：杨波，武汉科技大学理学院例2 背包问题 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 支支 配配

9、2008-09-01版权所有：杨波，武汉科技大学理学院例2 背包问题 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 2008-09-01版权所有：杨波，武汉科技大学理学院另一种求另一种求Si的推理过程的推理过程i123pi125wi234(Pi,Wi)x1x2x3(0,0)000(1,2)100(2,3)010(3,5)110(5,4)001(6,6)101(7,7)011(8,9)111KNAP(1,3,X)(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)2008-09-01版权所有：杨波，武汉科技大学理学院另一种求另一

10、种求Si的推理过程的推理过程nx1,x2,xn有2n个不同的0、1序列。对于每一个序列，若把 记为Wj，记为Pj，则此序列产生一对与之对应的序偶(Pj,Wj)。n在2n个序偶中，满足WjM，且使Pj取最大值得序偶就是背包问题的最优解。n用动态规划的向后处理法求解时，假定Si-1是以下序偶所组成的集合，这些序偶是由x1,x2,xi-1的2i-1个决策序列中一些可能的序列所组成的序偶(Pj,Wj)。nSi可按下述步骤得到。在xi=0的情况下，产生的序偶与Si-1相同。而在xi=1的情况下，产生的序偶是将(pi,wi)加到Si-1的每一对序偶(Pj,Wj)得到的，这序偶集就是 。然后按支配规则将Si

11、-1和 归并在一起就得到Si。2008-09-01版权所有：杨波，武汉科技大学理学院支配规则的正确性支配规则的正确性2008-09-01版权所有：杨波，武汉科技大学理学院KNAP(1,n,M)的求解的求解1.生成序偶集Si（应将WM的那些序偶(P,W)去掉，因为由它们不能导出满足约束条件的可行解。）。2.Si是背包问题KNAP(1,i,X)在0XM各种取值下的最优解。3.通过计算Sn可以找到KNAP(1,n,X)，0XM的所有解。KNAP(1,n,M)的最优解由Sn的最后一对序偶的P值给出。2008-09-01版权所有：杨波，武汉科技大学理学院KNAP(1,n,M)的求解的求解4.Sn的最末序

12、偶或者是的Sn-1最末序偶，或者是(Pj+pn,Wj+wn)，其中(Pj,Wj)Sn-1且Wj是Sn-1中满足Wj+wnM的最大值。通常情况下只需求此值，而不需要算出Sn中每个元素。5.若已找到Sn的最末序偶(Pl,Wl)，那么使pixi=Pl，wixi=Wl的x1,x2,xn的决策值可以通过检索这些Si来确定。2008-09-01版权所有：杨波，武汉科技大学理学院决策序列的推导决策序列的推导2008-09-01版权所有：杨波，武汉科技大学理学院决策序列的推导决策序列的推导的最后序偶2008-09-01版权所有：杨波，武汉科技大学理学院例3 S0=(0,0)S1=(0,0),(1,2)S2=(

13、0,0),(1,2),(2,3),(3,5)S3=(0,0),(1,2),(2,3),(5,4),(6,6),(7,7),(8,9)M=6，f3(6)由S3中的最后序偶(6,6)给出。1)(6,6)S2 x3=1 2)(6-p3,6-w3)=(1,2)S2且(1,2)S1 x2=0 3)(1,2)S0 x1=12008-09-01版权所有：杨波，武汉科技大学理学院 void DKP(p,w,n,M)S0=(0,0)for(i=1;i=n-1;i+)=(P1,W1)|(P1-pi,W1-wi)Si-1 and W1M /生成 /Si=MERGE-PURGE(Si-1,)/将Si-1和 归并为Si

14、/(PX,WX)=Sn-1的最末一个有效序偶 (PY,WY)=(P1pn,W1+wn)，其中，W1是Sn-1中使得WwnM的 所有序偶中取最大值的W /沿Sn-1,S1回溯确定xn,xn-1,x1的取值/if PXPY xn=0 /PX将是Sn的最末序偶/else xn=1 /PY将是Sn的最末序偶/回溯确定xn-1,x1 求Sn中最末序偶非形式的背包算法非形式的背包算法2008-09-01版权所有：杨波，武汉科技大学理学院1)序偶集Si的存储结构 使用两个一维数组P和W存放所有的序偶(P1,W1),其中P存放P1值，W存放W1值 序偶集S0,S1,Sn-1顺序、连续地存放于P和W中；用指针F

15、(i)表示Si中第一个元素在数组(P,W)中的下标位置，0in;F(n)Sn-1中最末元素位置1 1 2 3 4 5 6 7 P 0 0 1 0 1 2 3 W 0 0 2 0 2 3 5 F(0)F(1)F(2)F(3)DKP的实现的实现2008-09-01版权所有：杨波，武汉科技大学理学院2)序偶的生成与合并 Si的序偶将按照P和W的递增次序生成 中序偶的生成将与 和Si-1的合并同时进行 设 生成的下一序偶是(PQ,WQ)；对所有的(PQ,WQ)，根据支配规则处理如下：将Si-1中所有W值小于WQ的序偶直接计入Si中；根据支配规则，若Si-1中有W值小于WQ的序偶支配(PQ,WQ)，则(

16、PQ,WQ)将被舍弃，否则(PQ,WQ)计入Si中；并清除 Si-1中所有可被支配的序偶，这些序偶有WWQ且PPQ 对所有的(PQ,WQ)重复上述处理；将最后Si-1中剩余的序偶直接计入Si中；所有计入Si中的新序偶依次存放到由F(i)指示的Si的存放位置上。注：不需要存放 的专用空间2008-09-01版权所有：杨波，武汉科技大学理学院3)算法的实现 0/1背包问题的算法描述void DKNAP(double p,double w,int n,double M,int m)/p为效益值，w为相应的重量，n物品数，m为（P,M）对的最大数，double P=new doublem+2;doub

17、le W=new doublem+2;int F=new intn;int l,h,u,i,j,p,k,next;/l是 Si-1 中 第一对序偶的指针，而h是 Si-1 中最末序偶的指针 /u提供了在S1i中不用产生的序偶指示的最小值减1/k为 Si-1 中（P,W）组的指针；next为Si中（P,W）组的指针F0=1;W1=P1=0;l=h=1;/S0的首端和末端F1=next=2;/S1中的数对（P,W）将要存放的第一个空位置，/next指示存放位置for(i=1;i=n-1;i+)/生成Si k=l;/k指向Si-1 中第一对（P,W），k结束于h u=在lrh中使得的Wr+wi=M最

18、大的r/生成S1i同时生成Si 时去掉不满足约束条件的序偶 2008-09-01版权所有：杨波，武汉科技大学理学院for(j=l;j=u;j+)/生成S1i及归并为Si pp=Pj+pi;ww=Wj+wi;/由Si-1中的数对（P,W）计算S1i中下个数对 while(k=h)&(Wkww)/从Si-1取元素来归并（因为小于ww的可直接归并）Pnext=Pk;Wnext=Wk;next+;k+;if(kPnext-1)/(pp,ww)不受支配 Pnext=pp;Wnext=ww;next+;while(k=h)&(Pk=Pnext-1)/Wk,Pk受支配，清除 k+;while(k=h)/将S

19、i-1中剩余元素并入 Si Pnext=Pk;Wnext=Wk;next+;k+;l=h+l;h=next-1;F(i+1)=next;/对Si+1置初值 PARTS;/求解装包方案在此省略2008-09-01版权所有：杨波，武汉科技大学理学院4.过程DKNAP的分析1)空间复杂度 记Si中的序偶数为：|Si|则有，|Si|Si-1|又，|Si-1|所以，|Si|2|Si-1|最坏情况下，由Si-1生成 以及生成Si时没有序偶被支配，则 故，DKNAP所需的空间复杂度（P、W数组）为:(2n)2008-09-01版权所有：杨波，武汉科技大学理学院2)时间复杂度 由Si-1生成Si的时间为：，0

20、in-1 故，DKNAP计算所有的Si所需的时间为：进一步考察：若每件物品的重量wi和效益值pi均为整数，则Si中每个序偶(P,W)的P值和W值也是整数，且有 ，WM 又，在任一Si中，所有序偶具有互异P值和W值，故有 且 至少有一个（0,0）2008-09-01版权所有：杨波，武汉科技大学理学院 故，在所有wj和pj均为整数的情况下，DKNAP的时间和空间复杂度将为：2008-09-01版权所有：杨波，武汉科技大学理学院序偶集合的一种启发式生成策略 在由S0生成Sn-1的过程中，有些序偶无论如何也不会导致问题的最优解，这些序偶最终也不会出现在任何最优决策序列中，故可以及时的舍去，以进一步降低

21、计算量。原理如下：设L是最优解的估计值，但有fn(M)L 设PLEFT(i)=即i+1至n件物品的效益值之和 若正在生成的序偶(P,W)有PPLEFT(i)L，则(P,W)将不计入Si中。L的选择：取Si的最末序偶(P,W)的P作为L，Pfn(M)将某些剩余物品的p值与这个P值加在一起作为L2008-09-01版权所有：杨波，武汉科技大学理学院例6.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=0S1=0,100S2=0,50,100,150S3=0,2

22、0,50,70,100,120,150S4=0,10,20,30,50,60,70,80,100,110,120,130,150，160S5=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）表示2008-09-01版权所有：杨波，武汉科技大学理学院启发式规则求解 分析：将物品1,2,4,6装入背包，将占用163的重量并产生163的效益。故，取期望值L163.按照启发式生成规则，从Si中删除所有PP

23、LEFT(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 163n=6,(p1,p2,p3,p4,p5,p6)=(w1,w2,w3,w4,w5,w6)=(100,50,20,10,7,3),M=1652008-09-01版权所有：杨波，武汉科技大学理学院