0/1背包問題

1.二維數(shù)組解法

題目描述：有一個容量為m的背包，還有n個物品，他們的重量分別為w1、w2、w3.....wn，他們的價值分別為v1、v2、v3......vn。每個物品只能使用一次，求可以放進背包物品的最大價值。

輸入樣例：

10 4

2 1

3 3

4 5

7 9

輸出樣例：

12

解：

符號描述：i表示第i個物品，背包容量為j，dp[i][j]表示從下標(biāo)為0到i，背包容量為j時任意選取物品所得價值的最大值。所以全局的最優(yōu)解就是dp[m][n]

背包問題和函數(shù)的遞歸很像，只不過函數(shù)遞歸時從結(jié)果去接近邊界，而背包問題是從邊界出發(fā)，從小問題逐步去接近最終所要求的最優(yōu)解。

先創(chuàng)建一個二維數(shù)組

可以看到當(dāng)背包容量為零，或者可選物品為0時，他的局部最優(yōu)解都是0

然后從每一行的左到右開始遍歷（具體是為什么可以自己試一試）

- 當(dāng)背包容量為1時由于第一個物品的重量為2無法放進去，所以dp[1][1]=0;

- 當(dāng)背包容量為2時可以放進第一個物品，dp[2][1]=1;

- 當(dāng)背包容量大于2時，后續(xù)的最大價值都是1；

接著看第二行，這個第二行的含義就是當(dāng)背包物品容量從1到j(luò)變化時，任意選物品1-2的最優(yōu)解

先放的i=2的物品，然后看剩余重量能容納的上一行的局部最優(yōu)解。最后還要判斷是否這個最優(yōu)解比上一行同一列的最優(yōu)解更大，如果更大就更新狀態(tài)，否則就繼承狀態(tài)。

- j=1;dp[2][1]=0; 繼承上一行的狀態(tài)

- j=2;dp[2][2]=0; 0<1,繼承上一行的狀態(tài)

- j=3;dp[2][3]=3+dp[2][0]=3 ,3>1,更新狀態(tài)使dp[2][3]=3;

- j=4;dp[2][4]=3+dp[2][1]=3，同樣狀態(tài)更新

- j=5;dp[2][5]=3+dp[1][2]=4,4>1 狀態(tài)更新。

后面也是同理。

再看第三行

j從零到三無法當(dāng)下第三個物品，所以此時的最優(yōu)解依然是前兩個物品最優(yōu)選擇的最優(yōu)解，依舊繼承上一行的狀態(tài)。

然后從第4列開始，物品3就可以被放下

- j=4,dp[3][4]=5+dp[2][0]=5,5>3,狀態(tài)更新

- j=5,dp[3][5]=5+dp[2][1]=5,5>4,狀態(tài)更新

- j=6,dp[3][6]=5+dp[2][2]=6,6>4,狀態(tài)更新

我想你聰明如你已經(jīng)看到規(guī)律了，接著寫出第4行

所以得出來全局的最優(yōu)解就是12

下面來看代碼：

#include<iostream>
#include<algorithm>using namespace std;//學(xué)校的IDE有點老，好像不支持algorithm里的max
int max(int x,int y)
{return x>y?x:y;
}int m,n;
int dp[30][30]={0};//初始化全部設(shè)置為0
int w[30];//重量
int v[30];//價值
//0/1背包問題
int main()
{cin>>m>>n;int i=0,j=0;//輸入w,vfor(i=1;i<=n;i++){cin>>w[i]>>v[i];}//主要的循環(huán)體for(i=1;i<=n;i++)//物品編號遍歷{for(j=1;j<=m;j++)//背包重量遍歷{if(j<w[i])//這個物品無法放進去，繼承上一行的狀態(tài){dp[i][j]=dp[i-1][j];}else//判斷當(dāng)前最優(yōu)解與上一行的最優(yōu)解誰更大{dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);}}}cout<<dp[n][m]<<endl;return 0;
}

2.一維數(shù)組滾動解法

我們注意到二維數(shù)組的解法的時間復(fù)雜度是m*n，空間復(fù)雜度是m*n

而暴力求解的時間復(fù)雜度是2^n，空間復(fù)雜度也是m*n

二維數(shù)組法確實優(yōu)化的時間復(fù)雜度，但是空間復(fù)雜度卻和暴力一樣，因此便有了一維數(shù)組滾動解法來進一步優(yōu)化。

我們在上面的分析中，一步步的更新局部最優(yōu)解，最終得到所求的最優(yōu)解。但是有時候并沒有更新元素而是繼承上一行的最優(yōu)解，那么是不是就可以只用一個一維數(shù)組來存儲第i行的最優(yōu)解，然后需要更新的時候更新一下就可以了。

這時候我們就可以把原有的代碼稍作修改：

#include<iostream>
#include<algorithm>using namespace std;//學(xué)校的IDE有點老，好像不支持algorithm里的max
int max(int x,int y)
{return x>y?x:y;
}int m,n;
int dp[30]={0};//初始化全部設(shè)置為0
int w[30];//重量
int v[30];//價值
//0/1背包問題
int main()
{cin>>m>>n;int i=0,j=0;//輸入w,vfor(i=1;i<=n;i++){cin>>w[i]>>v[i];}//主要的循環(huán)體for(i=1;i<=n;i++){for(j=m;j>=w[i];j--)//從最右邊遍歷，后面的多重背包是從做左到右遍歷注意區(qū)分。{dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[m]<<endl;return 0;
}

電腦驗證

二維數(shù)組：

完全背包問題

題目描述：有一個容量為m的背包，還有n個物品，他們的重量分別為w1、w2、w3.....wn，他們的價值分別為v1、v2、v3......vn。每個物品有無限個，求可以放進背包物品的最大價值。

輸入樣例：10 4 2 1 3 3 4 6 8 10

輸出樣例：13

完全背包區(qū)別于0/1背包就是每個物品的選擇沒有次數(shù)限制。

它們的解題思路的區(qū)別在于主要的循環(huán)體那，完全背包需要先繼承上一層的狀態(tài)，然后考慮能不能放下，如果不能那這個位置的最優(yōu)解就是上層位置的最優(yōu)解，否則就把這個物品放進來，再加上背包容量為j-w[i]的同層位置的最優(yōu)解（同層是因為物品個數(shù)沒有限制），這樣就可以完成疊加。

二維數(shù)組法

來看代碼：

#include<iostream>
#include<algorithm>using namespace std;int m,n;
int dp[30][30]={0};
int w[30];
int v[30];
//完全背包問題 
int main()
{int i,j;//輸入m，ncin>>m>>n;// 輸入w，vfor(i=1;i<=n;i++){cin>>w[i]>>v[i];} //主要循環(huán)體 for(i=1;i<=n;i++){for(j=1;j<=m;j++){//完全背包要先繼承上一層狀態(tài)dp[i][j]=dp[i-1][j];if(j>=w[i]){dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);} }}cout<<dp[n][m]<<endl;return 0;
}

一維數(shù)組滾動解法

這個解法同樣也是為了降低空間復(fù)雜度

所以以同樣的方法優(yōu)化一下代碼：

#include<iostream>
#include<algorithm>using namespace std;int m,n;
int dp[30]={0};
int w[30];
int v[30];
//完全背包問題 
int main()
{int i,j;//輸入m，ncin>>m>>n;// 輸入w，vfor(i=1;i<=n;i++){cin>>w[i]>>v[i];} //主要循環(huán)體 for(i=1;i<=n;i++){for(j=w[i];j<=m;j++){dp[j]=max(dp[j],dp[j-w[i]]+v[i]);}}cout<<dp[m]<<endl;return 0;
}

電腦驗證

二維數(shù)組法：

一維數(shù)組滾動法：

多重背包問題

多重背包問題與前面兩個問題的區(qū)別也是在物品的數(shù)量上，這次它換成了有限個。

題目描述：有一個容量為m的背包，還有n個物品，他們的重量分別為w1、w2、w3.....wn，他們的價值分別為v1、v2、v3......vn，它們的數(shù)量分別有c1、c2、c3......cn個，求可以放進背包物品的最大價值。

輸入樣例：

10 3

2 1 6

6 10 3

3 6 3

輸出樣例：

轉(zhuǎn)換成傳統(tǒng)的0/1背包問題

這個方法比較容易想到，就不過多贅述了

看代碼：

#include<iostream>
#include<algorithm>using namespace std;int m,n;
int dp[30]={0};
int w[30];
int v[30];
int c[30];
int main()
{int i,j,k;//輸入m，ncin>>m>>n;//輸入w，v，c（數(shù)量） for(i=1;i<=n;i++){cin>>w[i]>>v[i]>>c[i];} for(i=1;i<=n;i++){for(k=1;k<=c[i];k++)//多次模擬0/1背包 {for(j=m;j>=w[i];j--)//一維滾動法 {dp[j]=max(dp[j],dp[j-w[i]]+v[i]);	 			}}}for(i=1;i<=m;i++)//這里直接電腦驗證了 {cout<<dp[i]<<" ";}cout<<endl;cout<<dp[m];return 0;} //10 3 2 1 6 6 10 3 3 6 3

特別感謝某站T_zhao 老師的講解，講的很明白。