0/1背包問(wèn)題

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

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

輸入樣例：

10 4

2 1

3 3

4 5

7 9

輸出樣例：

12

解：

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

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

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

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

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

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

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

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

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

先放的i=2的物品，然后看剩余重量能容納的上一行的局部最優(yōu)解。最后還要判斷是否這個(gè)最優(yōu)解比上一行同一列的最優(yōu)解更大，如果更大就更新?tīng)顟B(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īng)顟B(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從零到三無(wú)法當(dāng)下第三個(gè)物品，所以此時(shí)的最優(yōu)解依然是前兩個(gè)物品最優(yōu)選擇的最優(yōu)解，依舊繼承上一行的狀態(tài)。

然后從第4列開(kāi)始，物品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ī)律了，接著寫(xiě)出第4行

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

下面來(lái)看代碼：

#include<iostream>
#include<algorithm>using namespace std;//學(xué)校的IDE有點(diǎn)老，好像不支持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];//價(jià)值
//0/1背包問(wèn)題
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++)//物品編號(hào)遍歷{for(j=1;j<=m;j++)//背包重量遍歷{if(j<w[i])//這個(gè)物品無(wú)法放進(jìn)去，繼承上一行的狀態(tài){dp[i][j]=dp[i-1][j];}else//判斷當(dāng)前最優(yōu)解與上一行的最優(yōu)解誰(shuí)更大{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ù)組滾動(dòng)解法

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

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

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

我們?cè)谏厦娴姆治鲋?#xff0c;一步步的更新局部最優(yōu)解，最終得到所求的最優(yōu)解。但是有時(shí)候并沒(méi)有更新元素而是繼承上一行的最優(yōu)解，那么是不是就可以只用一個(gè)一維數(shù)組來(lái)存儲(chǔ)第i行的最優(yōu)解，然后需要更新的時(shí)候更新一下就可以了。

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

#include<iostream>
#include<algorithm>using namespace std;//學(xué)校的IDE有點(diǎn)老，好像不支持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];//價(jià)值
//0/1背包問(wèn)題
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;
}

電腦驗(yàn)證

二維數(shù)組：

完全背包問(wèn)題

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

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

輸出樣例：13

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

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

二維數(shù)組法

來(lái)看代碼：

#include<iostream>
#include<algorithm>using namespace std;int m,n;
int dp[30][30]={0};
int w[30];
int v[30];
//完全背包問(wèn)題 
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ù)組滾動(dòng)解法

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

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

#include<iostream>
#include<algorithm>using namespace std;int m,n;
int dp[30]={0};
int w[30];
int v[30];
//完全背包問(wèn)題 
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;
}

電腦驗(yàn)證

二維數(shù)組法：

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

多重背包問(wèn)題

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

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

輸入樣例：

10 3

2 1 6

6 10 3

3 6 3

輸出樣例：

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

這個(gè)方法比較容易想到，就不過(guò)多贅述了

看代碼：

#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--)//一維滾動(dòng)法 {dp[j]=max(dp[j],dp[j-w[i]]+v[i]);	 			}}}for(i=1;i<=m;i++)//這里直接電腦驗(yàn)證了 {cout<<dp[i]<<" ";}cout<<endl;cout<<dp[m];return 0;} //10 3 2 1 6 6 10 3 3 6 3

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