第3章動態(tài)規(guī)劃-背包問題

給定n種物品和一個背包，物品i的重量是wi，其價值為vi，背包的容量為C。背包問題是如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?如果在選擇裝入背包的物品時，對每種物品i只有兩種選擇：裝入背包或不裝入背包，即不能將物品i裝入背包多次，也不能只裝入物品i的一部分，則稱為0-1背包問題。3.100-1背包問題3.100-1背包問題考慮有三種物品,它們的重量為(w1,w2,w3)=(2,3,4),

價值為(v1,v2,v3)=(1,2,5),當(dāng)背包容量為c=6時，如何裝背包總價值最大？？{x1,x2,x3}={1,0,1}v1*x1+v2*x2+v3*x3=6{x1,x2,x3}={0,0,0}{0,0,1}{0,1,0}{1,0,0}{1,0,1}{1,1,0}常規(guī)方法：枚舉

在0-1背包問題中，物品i或者被裝入背包，或者不被裝入背包，設(shè)xi表示物品i裝入背包的情況，則當(dāng)xi=0時，表示物品i沒有被裝入背包，xi=1時，表示物品i被裝入背包。根據(jù)問題的要求，有如下約束條件和目標函數(shù)：（式1）（式2）問題歸結(jié)為尋找一個滿足約束條件式1，并使目標函數(shù)式2達到最大的解向量X=(x1,x2,…,xn)。3.100-1背包問題設(shè)(x1,x2,…,xn)是所給0-1背包問題的一個最優(yōu)解，則(x2,…,xn)是下面一個子問題的最優(yōu)解：如若不然，設(shè)(y2,…,yn)是上述子問題的一個最優(yōu)解，則，且。因此，，這說明(x1,y2,…,yn)是所給0-1背包問題比(x1,x2,…,xn)更優(yōu)的解，從而導(dǎo)致矛盾。背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)背包問題子問題的最優(yōu)值為m(i,j),即m(i,j)是背包容量為j，可選擇物品為i,i＋1,…,n時的最優(yōu)值。當(dāng)選擇第i個物品時，。

如果不選擇第i個物品，則。由背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，我們可以建立計算m(i,j)的遞歸式如下：m(i,j)=m(i+1,j-wi)+vim(i,j)=m(i+1,j)背包問題的遞歸關(guān)系背包問題算法描述voidKnapsack(Typev,intw,intc,intn,Type**m){intjMax=min(w[n]－1,c)//背包剩余容量//for(intj=0;j<=jMax;j++)//背包不同剩余容量jjMax<c//m[n][j]=0;for(intj=w[n];j<=c;j++)//背包不同剩余容量j>c//m[n][j]=v[n];for(inti=n-1;i>1;i--){jMax=min(w[i]-1,c);for(intj=0;j<=jMax;j++)//背包不同剩余容量j

jMax<c//m[i][j]=m[i+1][j];//沒產(chǎn)生任何效益//for(intj=w[i];j<=c;j++)//背包不同剩余容量j-wi

>c//m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);

}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);}voidTraceback(Type**m,intw,intc,intn,intx){for(inti=1;i<n;i++)if(m[i][c]==m[i+1][c])x[i]=0;else{x[i]=1;c=c-w[i];}x[n]=(m[n][c])?1:0;}背包問題算法描述算法復(fù)雜度分析：從m(i，j)的遞歸式容易看出，算法Knapsack需要O(nc)計算時間;Traceback需O(n)計算時間；算法總體需要O(nc)計算時間。當(dāng)背包容量c很大時，算法需要的計算時間較多。例如，當(dāng)c>2n時，算法需要Ω(n2n)計算時間。例:四個物品，背包容積為5，w[4]={2,1,3,2}，v[4]={12,10,20,15}，求最大價值m[1][c]及選取的物品編號4321432105000001015151515151520203535302537ijx4X3X2X11m[1][5]>m[2][5]所以物品1被選c–w[1]=3,查看m[2][3]>m[3][3]1j–w[2]=2,查看m[3][2]=m[4][2]0查看m[4][2]>01一個簡單的例子m[1][5]<>m[2][5]4321432105000001010151515151520203535302537ij構(gòu)造最優(yōu)解x[1]=1c=5-w[1]=3m[2][3]<>m[3][3]x[2]=1c=3-w[2]=2m[3][2]=m[4][2]x[3]=0c=2m[4][2]<>0x[4]=10-1背包問題可以看作是決策一個序列(x1,x2,…,xn)，對任一變量xi的決策是決定xi=1還是xi=0。在對xi-1決策后，已確定了(x1,…,xi-1)，在決策xi時，問題處于下列兩種狀態(tài)之一：a.背包容量不足以裝入物品i，則xi=0背包不增加價值；b.背包容量可以裝入物品i，則xi=1背包的價值增加了vi。這兩種情況下背包價值的最大者應(yīng)該是對xi決策后的背包價值。背包問題解法二令m(i,j)表示在前i(1≤i≤n)個物品中能夠裝入容量為j（1≤j≤C）的背包中的物品的最大值，則可以得到如下動態(tài)規(guī)劃函數(shù)：

m(i,0)=

m(0,j)=0（式3）式3表明：把前面i個物品裝入容量為0的背包和把0個物品裝入容量為j的背包，得到的價值均為0。背包問題解法二式4的第一個式子表明：如果第i個物品的重量大于背包的容量，則裝入前i個物品得到的最大價值和裝入前i-1個物品得到的最大價值是相同的，即物品i不能裝入背包。（式4）背包問題解法二第二個式子表明：如果第i個物品的重量小于背包的容量，則會有以下兩種情況：（1）如果把第i個物品裝入背包，則背包中物品的價值等于把前i-1個物品裝入容量為j-wi的背包中的價值加上第i個物品的價值vi；（2）如果第i個物品沒有裝入背包，則背包中物品的價值就等于把前i-1個物品裝入容量為j的背包中所取得的價值。顯然，取二者中價值較大者作為把前i個物品裝入容量為j的背包中的最優(yōu)解。（式4）背包問題解法二第一階段，只裝入前1個物品，確定在各種情況下的背包能夠得到的最大價值；第二階段，只裝入前2個物品，確定在各種情況下的背包能夠得到的最大價值；依此類推，直到第n個階段。最后，m(n,C)便是在容量為C的背包中裝入n個物品時取得的最大價值。為了確定裝入背包的具體物品，從m(n,C)的值向前推，如果m(n,C)>m(n-1,C)，表明第n個物品被裝入背包，前n-1個物品被裝入容量為C-wn的背包中；否則，第n個物品沒有被裝入背包，前n-1個物品被裝入容量