算法分析與設(shè)計第六章3(01背包問題)

1、2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,第六章 動態(tài)規(guī)劃,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,問題描述 1) KNAP(1,j,X) 目標(biāo)函數(shù)： 約束條件： 0/1背包問題：KNAP(1,n,M) 最優(yōu)性原理對于0/1背包問題成立 求解策略：向后處理法,6.5 0/1背包問題,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,2) 向后遞推關(guān)系式 記fj(X)是KNAP(1,j,X)的最優(yōu)解，則fn(M)有 fn(M) = maxfn-1(M),fn-1(M-wn)+pn 對于任意的fi(X)，i0,有 fi(X) = maxfi-1(X),fi

2、-1(X-wi)+pi 遞推過程： 初始值 0 X0 f0(X)= X0 求出fi在所有可能的X取值情況下的值。 fn(M)=KNAP(1,n,M),2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,例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,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,例1 背包問題 n=3,(w1,w2,w3)=(2,3,

3、4),(p1,p2,p3)=(1,2,5)，M=6 遞推計算過程,解向量的推導(dǎo)（最優(yōu)的決策序列）,f3(M)=6,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,f1,f2,f3計算過程的圖解 (w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6,1,2,3,4,5,6,7,0,1,2,f0(x)=0,i: fi-1(x-wi) +pi,i=0:函數(shù)不存在,1,2,3,4,5,6,7,0,1,2,i1: f0(x-w1) + p1,1,2,3,4,5,6,7,0,1,2,f1(x),1,2,3,4,5,6,7,0,1,2,i2: f1(x-w2) + p

4、2,3,w,w,w,w,1,2,3,4,5,6,7,0,1,2,3,w,f2(x), fi-1(X-wi)+pi曲線的構(gòu)造：將fi-1(X)的曲線在X軸上右移wi個單位，然后上 移pi個單位而得到； fi(X)曲線的構(gòu)造：由fi-1(X) 和fi-1(X-wi)+pi的曲線按X相同時f取大值的規(guī) 則歸并而成,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,1,2,3,4,5,6,7,0,6,7,8,w,1,2,3,4,5,8,9,i3: f2(x-w3) + p3,1,2,3,4,5,6,7,0,6,7,8,w,1,2,3,4,5,8,9,f3(x),10,1,2,3,4,5,6,7

5、,0,1,2,i2: f1(x-w2) + p2,3,w,1,2,3,4,5,6,7,0,1,2,3,w,f2(x),2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,1,2,3,4,5,6,7,0,6,7,8,w,1,2,3,4,5,8,9,f3(x),10,p,(P,W),(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5),(Pj,Wj): Pj=fi(Wj),2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,1,2,3,4,5,6,7,0,6,7,8,w,1,2,3,4,5,8,9,f3(x),10,p,(P,W),(w1,w2,w3)=(2,3,

6、4),(p1,p2,p3)=(1,2,5),S2,S3 ?,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,p,1,2,3,4,5,6,7,0,6,7,8,w,1,2,3,4,5,8,9,f3(x),10,p,(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),S2,S3 ?,(0,0),(1,2),(2,3),(6,6),(7,7),(8,9),(5,4),(3,5),支配規(guī)則：如果Si-1和 之一有序偶(Pj,Wj)，另一有(Pk,Wk)，且有 Wj

7、Wk ，PjPk， 則序偶(Pj,Wj)將被舍棄。（即取最大值規(guī)則）。,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,記 fi的序偶集合為 Si = (Pj,Wj)|Wj是fi曲線中使得fi產(chǎn)生一次跳躍的X值， 0jr 即Pj=fi(Wj)，r是跳躍點個數(shù) (P0,W0)=(0,0) 若共有r個階躍值，則分別對應(yīng)r個(Pj,Wj)序偶， 1jr 若WjWj+1,則PjPj+1，0jr 若WjXWj+1，fi(X)=fi(Wj) 若XWr，fi(X)=fi(Wr),序偶表示,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院, Si的構(gòu)造 記 是fi-1(X-wi)+pi的所有

8、序偶的集合，則 其中，Si-1是fi-1的所有序偶的集合 Si的構(gòu)造：由Si-1和 按照支配規(guī)則合并而成。 支配規(guī)則：如果Si-1和 之一有序偶(Pj,Wj),另一有(Pk,Wk)， 且有 WjWk , Pj Pk， 則序偶(Pj,Wj)將被舍棄。 （即取最大值規(guī)則）。 注： Si中的序偶是背包問題KNAP(1,i,X)在X各種 取值下子問題的最優(yōu)解,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,例2 背包問題 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6,支 配,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,例2 背包問題

9、 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,另一種求Si的推理過程,KNAP(1,3,X),(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5),2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,另一種求Si的推理過程,x1,x2,xn有2n個不同的0、1序列。對于每一個序列，若把 記為Wj， 記為Pj，則此序列產(chǎn)生一對與之對應(yīng)的序偶(Pj,Wj)。 在2n個序偶中，滿足WjM，且使Pj取最大值得序偶就是背包問題的最優(yōu)解。 用動態(tài)規(guī)劃的向后處理法求解時，假定

10、Si-1是以下序偶所組成的集合，這些序偶是由x1,x2,xi-1的2i-1個決策序列中一些可能的序列所組成的序偶(Pj,Wj)。 Si可按下述步驟得到。在xi=0的情況下，產(chǎn)生的序偶與Si-1相同。而在xi=1的情況下，產(chǎn)生的序偶是將(pi,wi)加到Si-1的每一對序偶(Pj,Wj)得到的，這序偶集就是 。然后按支配規(guī)則將Si-1和 歸并在一起就得到Si。,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,支配規(guī)則的正確性,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,KNAP(1,n,M)的求解,生成序偶集Si（應(yīng)將WM的那些序偶(P,W)去掉 ，因為由它們不能導(dǎo)出滿足

11、約束條件的可行解。 ）。 Si是背包問題KNAP(1,i,X)在0XM各種取值下的最優(yōu)解。 通過計算Sn可以找到KNAP(1,n,X)，0XM的所有解。 KNAP(1,n,M)的最優(yōu)解由Sn的最后一對序偶的P值給出。,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,KNAP(1,n,M)的求解,Sn的最末序偶或者是的Sn-1最末序偶，或者是 (Pj+pn,Wj+wn)，其中(Pj,Wj)Sn-1且Wj是Sn-1中滿足Wj+wnM的最大值。通常情況下只需求此值，而不需要算出Sn中每個元素。 若已找到Sn的最末序偶(Pl,Wl)，那么使pixi=Pl，wixi=Wl的x1,x2,xn的決

12、策值可以通過檢索這些Si來確定。,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,決策序列的推導(dǎo),2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,決策序列的推導(dǎo),的最后序偶,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,例3 S0=(0,0) S1=(0,0),(1,2) S2=(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)

13、S1 x2=0 3) (1,2) S0 x1=1,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,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/ (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

14、/PX將是Sn的最末序偶/ else xn=1 /PY將是Sn的最末序偶/ 回溯確定xn-1,x1 ,求Sn中最末序偶,非形式的背包算法,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,1)序偶集Si的存儲結(jié)構(gòu) 使用兩個一維數(shù)組P和W存放所有的序偶(P1,W1),其中P存放P1值，W存放W1值 序偶集S0, S1, Sn-1順序、連續(xù)地存放于P和W中； 用指針F(i)表示Si中第一個元素在數(shù)組(P,W)中的下標(biāo)位置，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

15、),DKP的實現(xiàn),2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,2) 序偶的生成與合并 Si的序偶將按照P和W的遞增次序生成 中序偶的生成將與 和Si-1的合并同時進(jìn)行 設(shè) 生成的下一序偶是(PQ,WQ)；對所有的(PQ,WQ)，根據(jù)支配規(guī)則處理如下： 將Si-1中所有W值小于WQ的序偶直接計入Si中； 根據(jù)支配規(guī)則，若Si-1中有W值小于WQ的序偶支配(PQ,WQ)， 則(PQ,WQ)將被舍棄，否則(PQ,WQ)計入Si中；并清除 Si-1中所有可被支配的序偶，這些序偶有WWQ且PPQ 對所有的(PQ,WQ)重復(fù)上述處理； 將最后Si-1中剩余的序偶直接計入Si中； 所有計入Si

16、中的新序偶依次存放到由F(i)指示的Si的存放位置上。 注：不需要存放 的專用空間,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,3) 算法的實現(xiàn) 0/1背包問題的算法描述 void DKNAP(double p,double w,int n,double M,int m) /p為效益值，w為相應(yīng)的重量，n物品數(shù)，m為（P,M）對的最大數(shù)， double P=new doublem+2; double W=new doublem+2; int F=new intn; int l,h,u,i,j,p,k,next; / l是 Si-1 中 第一對序偶的指針，而h是 Si-1 中最末序

17、偶的指針 /u提供了在S1i中不用產(chǎn)生的序偶指示的最小值減1 /k為 Si-1 中（P,W）組的指針；next為Si中（P,W）組的指針 F0=1;W1=P1=0; l=h=1; /S0的首端和末端 F1=next=2; /S1中的數(shù)對（P,W）將要存放的第一個空位置，/next指示存放位置 for(i=1;i=n-1;i+) /生成Si k=l; /k指向Si-1 中第一對（P,W），k結(jié)束于h u=在lrh中使得的Wr+wi=M最大的r /生成S1i同時生成Si 時去掉不滿足約束條件的序偶,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,for(j=l;jPnext-1) /(p

18、p,ww)不受支配 Pnext=pp;Wnext=ww;next+; while(k=h) / 求解裝包方案在此省略 ,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,4. 過程DKNAP的分析 1) 空間復(fù)雜度 記Si中的序偶數(shù)為：|Si| 則有， |Si| |Si-1| | 又， | | |Si-1| 所以， |Si|2|Si-1| 最壞情況下，由Si-1生成 以及生成Si時沒有序偶被支配，則 故，DKNAP所需的空間復(fù)雜度（P、W數(shù)組）為:(2n),2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,2) 時間復(fù)雜度 由Si-1生成Si的時間為： ，0in-1 故，DKN

19、AP計算所有的Si所需的時間為： 進(jìn)一步考察： 若每件物品的重量wi和效益值pi均為整數(shù)，則Si中每個序偶(P,W)的P值和W值也是整數(shù)，且有 ，WM 又，在任一Si中，所有序偶具有互異P值和W值，故有 且,至少有一個（0,0）,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,故，在所有wj和pj均為整數(shù)的情況下，DKNAP的時間和空間復(fù)雜度將為：,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,序偶集合的一種啟發(fā)式生成策略 在由S0生成Sn-1的過程中，有些序偶無論如何也不會導(dǎo)致問題的最優(yōu)解，這些序偶最終也不會出現(xiàn)在任何最優(yōu)決策序列中，故可以及時的舍去，以進(jìn)一步降低計算量。原理如下： 設(shè)L是最優(yōu)解的估計值，但有fn(M)L 設(shè)PLEFT(i)= 即i+1至n件物品的效益值之和 若正在生成的序偶(P,W)有PPLEFT(i)L，則(P,W)將不計入Si中。 L的選擇： 取Si的最末序偶(P,W)的P作為L，Pfn(M) 將某些剩余物品的p值與這個P值加在一起作為L,2008-09-01,版權(quán)所有：楊波，武漢科技大學(xué)理學(xué)院,例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 不使用啟發(fā)方法的序偶集 S0=