P01:?01背包問題

題目

有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。

基本思路

這是最基礎(chǔ)的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。

用子問題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

有必要將它詳細解釋一下：“將前i件物品放入容量為v的背包中”這個子問題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入容量為v的背包中”，價值為f[i-1][v]；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。

優(yōu)化空間復(fù)雜度

以上方法的時間和空間復(fù)雜度均為O(N*V)，其中時間復(fù)雜度基本已經(jīng)不能再優(yōu)化了，但空間復(fù)雜度卻可以優(yōu)化到O(V)。

先考慮上面講的基本思路如何實現(xiàn)，肯定是有一個主循環(huán)i=1..N，每次算出來二維數(shù)組f[i][0..V]的所有值。那么，如果只用一個數(shù)組f[0..V]，能不能保證第i次循環(huán)結(jié)束后f[v]中表示的就是我們定義的狀態(tài)f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環(huán)中推f[v]時）能夠得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事實上，這要求在每次主循環(huán)中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態(tài)f[i-1][v-c[i]]的值。（后面有詳細的圖解）偽代碼如下：

for?i=1..N

????for?v=V..0

????????f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當(dāng)于我們的轉(zhuǎn)移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因為現(xiàn)在的f[v-c[i]]就相當(dāng)于原來的f[i-1][v-c[i]]。如果將v的循環(huán)順序從上面的逆序改成順序的話，那么則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學(xué)習(xí)只用一維數(shù)組解01背包問題是十分必要的。

過程ZeroOnePack，表示處理一件01背包中的物品，兩個參數(shù)cost、weight分別表明這件物品的費用和價值。

procedure?ZeroOnePack(cost,weight)

????for?v=V..cost

????????f[v]=max{f[v],f[v-cost]+weight}

注意這個過程里的處理與前面給出的偽代碼有所不同。前面的示例程序?qū)懗蓈=V..0是為了在程序中體現(xiàn)每個狀態(tài)都按照方程求解了，避免不必要的思維復(fù)雜度。而這里既然已經(jīng)抽象成看作黑箱的過程了，就可以加入優(yōu)化。費用為cost的物品不會影響狀態(tài)f[0..cost-1]，這是顯然的。

有了這個過程以后，01背包問題的偽代碼就可以這樣寫：

for?i=1..N

????ZeroOnePack(c[i],w[i]);

初始化的細節(jié)問題

我們看到的求最優(yōu)解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時的最優(yōu)解，有的題目則并沒有要求必須把背包裝滿。一種區(qū)別這兩種問法的實現(xiàn)方法是在初始化的時候有所不同。

如果是第一種問法，要求恰好裝滿背包，那么在初始化時除了f[0]為0其它f[1..V]均設(shè)為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優(yōu)解。

如果并沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應(yīng)該將f[0..V]全部設(shè)為0。

為什么呢？可以這樣理解：初始化的f數(shù)組事實上就是在沒有任何物品可以放入背包時的合法狀態(tài)。如果要求背包恰好裝滿，那么此時只有容量為0的背包可能被價值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬于未定義的狀態(tài)，它們的值就都應(yīng)該是-∞了。如果背包并非必須被裝滿，那么任何容量的背包都有一個合法解“什么都不裝”，這個解的價值為0，所以初始時狀態(tài)的值也就全部為0了。

這個小技巧完全可以推廣到其它類型的背包問題，后面也就不再對進行狀態(tài)轉(zhuǎn)移之前的初始化進行講解。

小結(jié)

01背包問題是最基本的背包問題，它包含了背包問題中設(shè)計狀態(tài)、方程的最基本思想，另外，別的類型的背包問題往往也可以轉(zhuǎn)換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態(tài)轉(zhuǎn)移方程的意義，以及最后怎樣優(yōu)化的空間復(fù)雜度。

二維數(shù)組代碼的寫法

1 #include<bits/stdc++.h> 2 using namespace std; 3 int dp[1005][1005]; 4 int weight[1005]; 5 int value[1005]; 6 int main() 7 { 8 int n,m; 9 cin>>m>>n; 10 memset(dp,0,sizeof(dp));//數(shù)組清空,其實同時就把邊界給做了清理 11 for(int i=1; i<=n; i++) 12 cin>>weight[i]>>value[i]; 13 //從1開始有講究的因為涉及到dp[i-1][j],從0開始會越界 14 for(int i=1; i<=n; i++)//判斷每個物品能否放進 15 { 16 for(int j=0; j<=m; j++)//對每個狀態(tài)進行判斷 17 //這邊兩重for都可以倒著寫，只是需要處理最邊界的情況，滾動數(shù)組不一樣 18 { 19 if(j>=weight[i])//能放進 20 dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]); 21 22 else dp[i][j]=dp[i-1][j];//不能放進 23 } 24 } 25 cout<<dp[n][m]<<endl; 26 return 0; 27 }

這個數(shù)組開銷還是很大的，因為是二維的，萬一哪個數(shù)據(jù)一大，分分鐘內(nèi)存超限，所以我們要進行優(yōu)化。

3、空間優(yōu)化

　　空間優(yōu)化，每一次V(i)(j)改變的值只與V(i-1)(x) {x:1...j}有關(guān)，V(i-1)(x)是前一次i循環(huán)保存下來的值；

　　因此，可以將V縮減成一維數(shù)組，從而達到優(yōu)化空間的目的，狀態(tài)轉(zhuǎn)移方程轉(zhuǎn)換為?B(j)= max{B(j), B(j-w(i))+v(i)}；

　　并且，狀態(tài)轉(zhuǎn)移方程，每一次推導(dǎo)V(i)(j)是通過V(i-1)(j-w(i))來推導(dǎo)的，所以一維數(shù)組中j的掃描順序應(yīng)該從大到小(capacity到0)，否者前一次循環(huán)保存下來的值將會被修改，從而造成錯誤。

?

　　 同樣以上述例子中i=3時來說明，有:

　　　　1)?i=3，j=8，w(3)=4，v(3)=5，有j>w(3)，則B(8)=max｛B(8)，B(8-w(3))+v(3)｝=max｛B(8)，B(4)+5｝=max｛7，4+5｝=9；

　　　　2)?j- -即j=7，有j>w(3)，則B(7)=max｛B(7)，B(7-w(3))+v(3)｝=max｛B(7)，B(3)+5｝=max｛7，4+5｝=9；

　　　　3)?j- -即j=6，有j>w(3)，則B(6)=max｛B(6)，B(6-w(3))+v(3)｝=max｛B(6)，B(2)+5｝=max｛7，3+5｝=8；

　　　　4)?j- -即j=5，有j>w(3)，則B(5)=max｛B(5)，B(5-w(3))+v(3)｝=max｛B(5)，B(1)+5｝=max｛7，0+5｝=7；

　　　　5)?j- -即j=4，有j＝w(3)，則B(4)=max｛B(4)，B(4-w(3))+v(3)｝=max｛B(4)，B(0)+5｝=max｛4，0+5｝=5；

　　　　6)?j- -即j=3，有j<w(3)，繼續(xù)訪問數(shù)組會出現(xiàn)越界，所以本輪操作停止，B(0)到B(3)的值保留上輪循環(huán)（i=2時）的值不變，進入下一輪循環(huán)i++；

?

　　如果j不逆序而采用正序j=0...capacity，如上圖所示，當(dāng)j=8時應(yīng)該有B(8)=B(8-w(3))+v(3)=B(4)+5，然而此時的B(4)已經(jīng)在j=4的時候被修改過了，原來的B(4)=4，現(xiàn)在B(4)=5，所以計算得出B(8)=5+5=10，顯然這于正確答案不符合；所以該一維數(shù)組后面的值需要前面的值進行運算再改動，如果正序便利，則前面的值將有可能被修改掉從而造成后面數(shù)據(jù)的錯誤；相反如果逆序遍歷，先修改后面的數(shù)據(jù)再修改前面的數(shù)據(jù)，此種情況就不會出錯了；

這里用到的一維數(shù)組就是傳說中的---------------滾動數(shù)組！！！

什么是滾動數(shù)組。

說白了二維數(shù)組只是把每個物品都跑一遍，然后到最后一個物品的時候輸出答案，那么過程值只是計算的時候用一次，我沒必要存下來。所以用一個數(shù)組去滾動存儲，然后用后一個狀態(tài)的值去覆蓋前面一個狀態(tài)。然后形象的叫它：滾動數(shù)組

用滾動數(shù)組求01背包的最重要的一點就是：第二層循環(huán)要逆序！！！如上圖圖解，代碼如下：

1 #include<bits/stdc++.h> 2 using namespace std; 3 int dp[1005];//滾動數(shù)組的寫法，省下空間省不去時間 4 int weight[1005]; 5 int value[1005]; 6 int main() 7 { 8 int n,m; 9 cin>>m>>n; 10 memset(dp,0,sizeof(dp)); 11 for(int i=1; i<=n; i++) 12 cin>>weight[i]>>value[i]; 13 for(int i=1; i<=n; i++)//對每個數(shù)判斷，可反 14 { 15 for(int j=m; j>=weight[i]; j--)//這里這個循環(huán)定死，不能反,反了就是完全背包 16 { 17 dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);//其實不斷在判斷最優(yōu)解，一層一層的 18 } 19 } 20 cout<<dp[m]<<endl; 21 return 0; 22 }

?

P02: 完全背包問題

題目 有N種物品和一個容量為V的背包。第i種物品有若干件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本思路:

?這個問題和我們剛解決的01背包問題很像,不同的是該問題中的物品每一件有若干件,而01背包中的每一件物品只有一件.

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

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

?????? 與01背包相同，完全背包也需要求出NV個狀態(tài)F[i][j]。但是完全背包求F[i][j]時需要對k分別取0,…，j/C[i]求最大F[i][j]值,耗時為j/C[i]。那么總的時間復(fù)雜度為O(NV∑(j/C[i]))，代碼如下：

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=555; 4 int dp[maxn][111111]; 5 int need[maxn],value[maxn]; 6 int n,m; 7 int main() 8 { 9 int i,j,k; 10 while(~scanf("%d %d",&n,&m)) 11 { 12 memset(dp,0,sizeof(dp)); 13 for(i=1;i<=n;i++) 14 scanf("%d %d",&need[i],&value[i]); 15 for(i=1;i<=n;i++) 16 { 17 for(j=0;j<=m;j++) 18 { 19 for(k=0;k*need[i]<=j;k++) 20 dp[i][j]=max(dp[i][j],dp[i-1][j-k*need[i]]+k*value[i]); 21 } 22 } 23 printf("%d\n",dp[n][m]); 24 } 25 return 0; 26 }

?

優(yōu)化空間復(fù)雜度為O（V）

??????? 和01背包問題一樣，完全背包也可以用一維數(shù)組來保存數(shù)據(jù)。算法樣式和01背包的很相似，唯一不同的是對V遍歷時變?yōu)檎?#xff0c;而01背包為逆序

。01背包中逆序是因為F[i][]只和F[i-1][]有關(guān)，且第i件的物品加入不會對F[i-1][]狀態(tài)造成影響。而完全背包則考慮的是第i種物品的出現(xiàn)的問題，

第i種物品一旦出現(xiàn)它勢必應(yīng)該對第i種物品還沒出現(xiàn)的各狀態(tài)造成影響。也就是說，原來沒有第i種物品的情況下可能有一個最優(yōu)解，現(xiàn)在第i種物品

出現(xiàn)了，而它的加入有可能得到更優(yōu)解，所以之前的狀態(tài)需要進行改變，故需要正序。優(yōu)化后的代碼為：

1 [cpp] view plain copy 2 #include<bits/stdc++.h> 3 using namespace std; 4 const int maxn=555; 5 int dp[111111]; 6 int need[maxn],value[maxn]; 7 int n,m; 8 int main() 9 { 10 int i,j,k; 11 while(~scanf("%d %d",&n,&m)) 12 { 13 memset(dp,0,sizeof(dp)); 14 for(i=1;i<=n;i++) 15 scanf("%d %d",&need[i],&value[i]); 16 for(i=1;i<=n;i++) 17 { 18 for(j=need[i];j<=m;j++) 19 { 20 if(j>=need[i]) 21 dp[j]=max(dp[j],dp[j-need[i]]+value[i]); 22 } 23 } 24 printf("%d\n",dp[m]); 25 } 26 return 0; 27 }

?

兩者區(qū)別：

1.01背包：有n種物品與承重為m的背包。每種物品只有一件，每個物品都有對應(yīng)的重量weight[i]與價值value[i]，求解如何裝包使得價值最大。

2.完全背包：有n種物品與承重為m的背包。每種物品有無限多件，每個物品都有對應(yīng)的重量weight[i]與價值value[i]，求解如何裝包使得價值最大。

P03: 多重背包問題

題目

有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

基本算法

這題目和完全背包問題很類似。基本的方程只需將完全背包問題的方程略微一改即可，因為對于第i種物品有n[i]+1種策略：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權(quán)值，則有狀態(tài)轉(zhuǎn)移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

復(fù)雜度是O(V*Σn[i])。用完全背包思想實現(xiàn)的代碼如下：

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1005; 4 5 int dp[N]; 6 int c[N],w[N],num[N]; 7 int n,m; 8 9 void ZeroOne_Pack(int cost,int weight,int n)//吧01背包封裝成函數(shù) 10 { 11 for(int i=n; i>=cost; i--) 12 dp[i] = max(dp[i],dp[i-cost] + weight); 13 } 14 15 void Complete_Pack(int cost,int weight,int n)//把完全背包封裝成函數(shù) 16 { 17 for(int i=cost; i<=n; i++) 18 dp[i] = max(dp[i],dp[i-cost] + weight); 19 } 20 21 int Multi_Pack(int c[],int w[],int num[],int n,int m)//多重背包 22 { 23 memset(dp,0,sizeof(dp)); 24 for(int i=1; i<=n; i++)//遍歷每種物品 25 { 26 if(num[i]*c[i] > m) 27 Complete_Pack(c[i],w[i],m); 28 //如果全裝進去已經(jīng)超了重量，相當(dāng)于這個物品就是無限的 29 //因為是取不光的。那么就用完全背包去套 30 else 31 { 32 int k = 1; 33 //取得光的話，去遍歷每種取法 34 //這里用到是二進制思想，降低了復(fù)雜度 35 //為什么呢，因為他取的1,2,4,8...與余數(shù)個該物品，打包成一個大型的該物品 36 //這樣足夠湊出了從0-k個該物品取法 37 //把復(fù)雜度從k變成了logk 38 //如k=11，則有1,2,4,4，足夠湊出0-11個該物品的取法 39 while(k < num[i]) 40 { 41 ZeroOne_Pack(k*c[i],k*w[i],m); 42 num[i] -= k; 43 k <<= 1; 44 } 45 ZeroOne_Pack(num[i]*c[i],num[i]*w[i],m); 46 } 47 } 48 return dp[m]; 49 } 50 51 int main() 52 { 53 int t; 54 cin>>t; 55 while(t--) 56 { 57 cin>>m>>n; 58 for(int i=1; i<=n; i++) 59 cin>>c[i]>>w[i]>>num[i]; 60 cout<<Multi_Pack(c,w,num,n,m)<<endl; 61 } 62 return 0; 63 }

另一種好想好寫的基本方法是轉(zhuǎn)化為01背包求解：把第i種物品換成n[i]件01背包中的物品，則得到了物品數(shù)為Σn[i]的01背包問題，直接求解，復(fù)雜度仍然是O(V*Σn[i])。

首先這種可以把物品拆開，把相同的num[i]件物品 看成 價值跟重量相同的num[i]件不同的物品，那么！！是不是就轉(zhuǎn)化成了一個規(guī)模稍微大一點的01背包了。對不對？

1 #include<bits/stdc++.h> 2 using namespace std; 3 int dp[1005]; 4 int weight[1005],value[1005],num[1005]; 5 int main() 6 { 7 int n,m; 8 cin>>n>>m; 9 memset(dp,0,sizeof(dp)); 10 for(int i=1; i<=n; i++) 11 cin>>weight[i]>>value[i]>>num[i]; 12 13 for(int i=1; i<=n; i++)//每種物品 14 15 for(int k=0; k<num[i]; k++)//其實就是把這類物品展開，調(diào)用num[i]次01背包代碼 16 17 for(int j=m; j>=weight[i]; j--)//正常的01背包代碼 18 19 dp[j]=max(dp[j],dp[j-weight[i]]+value[i]); 20 21 cout<<dp[m]<<endl; 22 return 0; 23 }

?

但是我們期望將它轉(zhuǎn)化為01背包問題之后能夠像完全背包一樣降低復(fù)雜度。仍然考慮二進制的思想，我們考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0..n[i]件——均能等價于取若干件代換以后的物品。另外，取超過n[i]件的策略必不能出現(xiàn)。

方法是：將第i種物品分成若干件物品，其中每件物品有一個系數(shù)，這件物品的費用和價值均是原來的費用和價值乘以這個系數(shù)。使這些系數(shù)分別為1,2,4,...,2^(k-1),n[i]-2^k+1，且k是滿足n[i]-2^k+1>0的最大整數(shù)。例如，如果n[i]為13，就將這種物品分成系數(shù)分別為1,2,4,6的四件物品。

分成的這幾件物品的系數(shù)和為n[i]，表明不可能取多于n[i]件的第i種物品。另外這種方法也能保證對于0..n[i]間的每一個整數(shù)，均可以用若干個系數(shù)的和表示，這個證明可以分0..2^k-1和2^k..n[i]兩段來分別討論得出，并不難，希望你自己思考嘗試一下。

這樣就將第i種物品分成了O(log?n[i])種物品，將原問題轉(zhuǎn)化為了復(fù)雜度為O(V*Σlog?n[i])的01背包問題，是很大的改進。

下面給出O(log?amount)時間處理一件多重背包中物品的過程，其中amount表示物品的數(shù)量：

procedure?MultiplePack(cost,weight,amount)

????if?cost*amount>=V

????????CompletePack(cost,weight)

????????return

????integer?k=1

????while?k<num

????????ZeroOnePack(k*cost,k*weight)

????????amount=amount-k

????????k=k*2

????ZeroOnePack(amount*cost,amount*weight)

希望你仔細體會這個偽代碼，如果不太理解的話，不妨翻譯成程序代碼以后，單步執(zhí)行幾次，或者頭腦加紙筆模擬一下，也許就會慢慢理解了。

參考資料：

http://blog.csdn.net/stack_queue/article/details/53544109（背包九講）

https://www.cnblogs.com/Christal-R/p/Dynamic_programming.html

http://blog.csdn.net/tinyguyyy/article/details/51203935

http://blog.csdn.net/howardemily/article/details/55223039

http://blog.csdn.net/aaakirito/article/details/54096907#

http://blog.csdn.net/carol123456/article/details/52155142

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

總結(jié)

以上是生活随笔為你收集整理的动态规划-----------01背包，完全背包与多重背包的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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