一、01背包問題

? 01背包是在M件物品取出若干件放在空間為W的背包里，每件物品的體積為C₁，C₂，…，C_n，與之相對應(yīng)的價值為W₁,W₂，…，W_n.求解將那些物品裝入背包可使總價值最大。

? 動態(tài)規(guī)劃：

? 1） 子問題定義：F[i][j]表示前i件物品中選取若干件物品放入剩余空間為j的背包中所能得到的最大價值。

? 2） 根據(jù)第i件物品放或不放進(jìn)行決策

? ? ? ? ? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ? ? ??

其中F[i-1][j]表示前i-1件物品中選取若干件物品放入剩余空間為j的背包中所能得到的最大價值；

而F[i-1][j-C[i]]+W[i]表示前i-1件物品中選取若干件物品放入剩余空間為j-C[i]的背包中所能取得的最大價值加上第i件物品的價值

根據(jù)第i件物品放或是不放確定遍歷到第i件物品時的狀態(tài)F[i][j]。

設(shè)物品件數(shù)為N，背包容量為V，第i件物品體積為C[i]，第i件物品價值為W[i]。

由此寫出偽代碼如下：

1 F[0][] ← {0} 2 3 F[][0] ← {0} 4 5 for i←1 to N 6 7 do for k←1 to V 8 9 F[i][k] ← F[i-1][k] 10 11 if(k >= C[i]) 12 13 then F[i][k] ← max(F[i][k],F[i-1][k-C[i]]+W[i]) 14 15 return F[N][V]

上述代碼9-13行也可以這樣寫：

if(k<C[i])//如果第i個物品的體積已經(jīng)大于背包剩余容量then F[i][k] ← F[i-1][k] else F[i][k] ← max(F[i-1][k],F[i-1][k-C[i]]+W[i])

理解為：當(dāng)?shù)趇個物品的體積大于背包剩余容量時，第i個物品肯定不能被放進(jìn)去，所以F[i][k]=F[i-1][k]，

而當(dāng)?shù)趇個物品的體積小于或等于背包剩余容量時,可以有兩種選擇，放第i個物品(F[i-1][k-C[i]]+W[i])或者不放(F[i-1][k])，然后選擇兩者之間最優(yōu)的。

而寫成第一種等價的偽代碼是為了更好的理解從二維數(shù)組解法到一維數(shù)組解法的轉(zhuǎn)換。

?根據(jù)算法求出的最大價值表本身其實含有位置信息，從F[N][V]逆著走向F[0][0]，設(shè)i=N,j=V，如果F[i][j]==F[i-1][j-C[i]]+W[i]說明包里面有第i件物品，同時j -= C[i]，不管F[i][j]與F[i-1][j-C[i]]+W[i]相不相等i都要減1，因為01背包的第i件物品要么放要么不放，不管放還是不放其已經(jīng)遍歷過了，需要繼續(xù)往下遍歷。

打印背包內(nèi)物品的偽代碼如下：

1 i←N 2 3 j←V 4 5 while(i>0 && j>0) 6 7 do if(F[i][j]=F[i-1][j-C[i]]+W[i]) 8 9 then Print W[i] 10 11 j←j-C[i] 12 13 i←i-1

也可以定義一個二維數(shù)組Path[N][V]來存放背包內(nèi)物品信息，開始時Path[N][V]初始化為0,當(dāng) F[i][j]==F[i-1][j-C[i]]+W[i]時Path[i][j]置1。最后通過從Path[N+1][V+1]逆著走向Path[0][0]來獲取背包內(nèi)物品。其中Path[0][]與Path[][0]為邊界。

??????? 加入路徑信息的偽代碼如下：

F[0][] ← {0}F[][0] ← {0}Path[][] ← 0for i←1 to Ndo for k←1 to VF[i][k] ← F[i-1][k]if(k >= C[i] && F[i][k] < F[i-1][k-C[i]]+W[i])then F[i][k] ← F[i-1][k-C[i]]+W[i]Path[i][k] ← 1return F[N][V] and Path[][]

打印背包內(nèi)物品的偽代碼如下：

i←Nj←Vwhile(i>0 && j>0)do if(Path[i][j] = 1)then Print W[i]j←j-C[i]i←i-1

將使用二位數(shù)組改為使用一維數(shù)組：

觀察偽代碼可也發(fā)現(xiàn)，F[i][j]只與F[i-1][j]和F[i-1][j-C[i]]有關(guān)，即只和i-1時刻狀態(tài)有關(guān)，所以我們只需要用一維數(shù)組F[]來保存i-1時的狀態(tài)F[]。假設(shè)i-1時刻的F[]為{a₀，a₁，a₂，…，a_v}，難么i時刻的F[]中第k個應(yīng)該為max(a_k,a_k-C[i]+W[i])即max(F[k],F[k-C[i]]+W[i])，這就需要我們遍歷V時逆序遍歷，這樣才能保證求i時刻F[k]時F[k-C[i]]是i-1時刻的值。如果正序遍歷則當(dāng)求F[k]時其前面的F[0],F[1]，…，F[K-1]都已經(jīng)改變過，里面存的都不是i-1時刻的值，這樣求F[k]時利用F[K-C[i]]必定是錯的值。最后F[V]即為最大價值。

求F[j]的狀態(tài)方程如下：

????????????????????????????? ? ? ? ? ? ? ?

偽代碼如下：

1 F[] ← {0} 2 3 for i ← 1 to N 4 5 do for k ← V to C[i] 6 7 F[k] ← max(F[k],F[k-C[i]]+W[i]) 8 9 return F[V]

加入路徑信息的偽代碼如下：

1 F[] ← {0} 2 3 Path[][]←0 4 5 for i←1 to N 6 7 do for k←V to C[i] 8 9 if(F[k] < F[k-C[i]]+W[i]) 10 11 then F[k] ← F[k-C[i]]+W[i] 12 13 Path[i][k] ← 1 14 15 return F[V] and Path[][]

?

二、物品無限的背包問題

將01背包一維數(shù)組解法中j的遍歷順序do for k←V to C[i]改為do for?k←C[i]?to V就變成了物品無限背包的解法。

1 F[] ← {0} 2 3 for i ← 1 to N 4 5 do for k ← C[i] to V 6 7 F[k] ← max(F[k],F[k-C[i]]+W[i]) 8 9 return F[V]

?三、完全背包(要求背包必須裝滿，而不是最大限度的裝)

主要是在01背包的初始化過程中的不同，然后考慮第i個物體的時候判斷下是否可以裝滿的條件

1 F[][] ← {-1} 2 3 F[][0] ← {0} 4 5 for i←1 to N 6 7 do for k←1 to V 8 if (F[i-1][k-C[i]]!=-1) 9 then 10 11 F[i][k] ← F[i-1][k] 12 13 if(k >= C[i]) 14 15 then F[i][k] ← max(F[i][k],F[i-1][k-C[i]]+W[i]) 16 17 return F[N][V]

?

四、代碼實際操練：

二維數(shù)組解法：

01背包問題具體例子：先輸入兩個數(shù)n,V表示物品的個數(shù)和背包的容量，接下來輸入n組數(shù)據(jù)代表n種物品，每組數(shù)據(jù)有兩個值對應(yīng)物品的體積和價值，每種物品只有一個，求在背包容量下能裝物品最大價值，并求出最大價值下，組合中各個物品的價值？

#include<iostream> using namespace std; const int N_max=100;//物品個數(shù)上限 const int V_max=100;//背包容量上限 int dp[N_max][V_max]; bool flag[N_max][V_max]; int main() {int n;//實際輸入物品的個數(shù)cin>>n;int V;//背包的實際容量cin>>V;int *v=new int[n+1];int *price=new int[n+1];//輸入n組數(shù)據(jù)，分別為體積v和價值price//注意這里要從1開始for(int i=1;i<=n;i++){cin>>v[i]>>price[i];}//初始化dp數(shù)組//注意這里的=for(int i=0;i<=n;i++){dp[i][0]=0;}for(int i=0;i<=V;i++){dp[0][i]=0;}//初始化flag數(shù)組memset(flag,false,(n+1)*(V+1)*sizeof(bool));//開始遞推for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){dp[i][j]=dp[i-1][j];if(v[i]<=j && dp[i-1][j-v[i]]+price[i]>dp[i][j])//放下該物品 {dp[i][j]=dp[i-1][j-v[i]]+price[i];flag[i][j]=true;}} }cout<<"能容下的最大價值是:"<<dp[n][V]<<endl;cout<<"組成最佳值的物品價值如下:"<<endl;int i=n;int j=V;while(i>=0 && j>=0){if(flag[i][j]){cout<<price[i]<<endl;j=j-v[i];}i--;}return 0; }

一維數(shù)組的解法：

#include<iostream> using namespace std; bool flag[100][100]={false}; int main() {int n;//實際輸入物品的個數(shù)cin>>n;int V;//背包的實際容量cin>>V;int *dp=new int[V+1];int *v=new int[n+1];int *price=new int[n+1];//輸入n組數(shù)據(jù)，分別為體積v和價值price//注意這里要從1開始for(int i=1;i<=n;i++){cin>>v[i]>>price[i];}//初始化dp數(shù)組memset(dp,0,(V+1)*sizeof(int));//開始遞推for(int i=1;i<=n;i++){for(int j=V;j>=v[i];j--)//for(int j=v[i];j<=V;j++) {if( dp[j-v[i]]+price[i]>dp[j])//放下該物品 {dp[j]=dp[j-v[i]]+price[i];flag[i][j]=true;}} }cout<<"能容下的最大價值是:"<<dp[V]<<endl;cout<<"組成最佳值的物品價值如下:"<<endl;int i=n;int j=V;while(i>=0 && j>=0){if(flag[i][j]){cout<<price[i]<<endl;j=j-v[i];}i--;}return 0; }

調(diào)試結(jié)果：

?

?

物品無限背包問題具體例子：先輸入兩個數(shù)n,V表示物品的個數(shù)和背包的容量，接下來輸入n組數(shù)據(jù)代表n種物品，每組數(shù)據(jù)有兩個值對應(yīng)物品的體積和價值，每種物品有無限個，求在背包容量下能裝物品最大價值，并求出最大價值下，組合中各個物品的價值？

#include<iostream> #include<algorithm> #include<vector> using namespace std; bool flag[100][100]={false}; int main() {int n;//實際輸入物品的個數(shù)cin>>n;int V;//背包的實際容量cin>>V;int *dp=new int[V+1];int *v=new int[n+1];int *price=new int[n+1];//輸入n組數(shù)據(jù)，分別為體積v和價值price//注意這里要從1開始for(int i=1;i<=n;i++){cin>>v[i]>>price[i];}//初始化dp數(shù)組memset(dp,0,(V+1)*sizeof(int));//開始遞推for(int i=1;i<=n;i++){for(int j=v[i];j<=V;j++){if( dp[j-v[i]]+price[i]>dp[j])//放下該物品 {dp[j]=dp[j-v[i]]+price[i];flag[i][j]=true;}} }cout<<"能容下的最大價值是:"<<dp[V]<<endl;return 0; }

?01背包下恰好裝滿的例子：先輸入兩個數(shù)n,V表示物品的個數(shù)和背包的容量，接下來輸入n組數(shù)據(jù)代表n種物品，每組數(shù)據(jù)有兩個值對應(yīng)物品的體積和價值，每種物品只有一個，求在背包恰好裝滿時物品最大價值，并求出最大價值下，組合中各個物品的價值，若無法恰好裝滿，則輸出無法裝滿的提示語句？

#include<iostream> using namespace std; const int N_max=100;//物品個數(shù)上限 const int V_max=100;//背包容量上限 int dp[N_max][V_max]; bool flag[N_max][V_max]; int main() {int n;//實際輸入物品的個數(shù)cin>>n;int V;//背包的實際容量cin>>V;int *v=new int[n+1];int *price=new int[n+1];//輸入n組數(shù)據(jù)，分別為體積v和價值price//注意這里要從1開始for(int i=1;i<=n;i++){cin>>v[i]>>price[i];}//注意恰好裝滿與普通01背包的初始化條件是不同的memset(dp,-1,sizeof(dp));for(int i=0;i<=n;i++){dp[i][0]=0;}//初始化flag數(shù)組memset(flag,false,(n+1)*(V+1)*sizeof(bool));//開始遞推for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){//注意這里是恰好裝滿時的判斷條件if(dp[i-1][j-v[i]]!=-1){dp[i][j]=dp[i-1][j];if(v[i]<=j && dp[i-1][j-v[i]]+price[i]>dp[i][j])//放下該物品 {dp[i][j]=dp[i-1][j-v[i]]+price[i];flag[i][j]=true;}}} }if(dp[n][V]==-1){cout<<"沒法恰好裝滿";}else{cout<<"恰好裝滿時最大價值是:"<<dp[n][V]<<endl;cout<<"組成最佳值的物品價值如下:"<<endl;int i=n;int j=V;while(i>=0 && j>=0){if(flag[i][j]){cout<<price[i]<<endl;j=j-v[i];}i--;}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/bewolf/p/4776880.html

總結(jié)

以上是生活随笔為你收集整理的01背包及其变种(物品无限背包、恰好装满背包)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。