歡迎來到博主的專欄：算法解析
博主ID：代碼小號

牛客網——【模板】01背包

題目解析

關于I/O相關的東西博主就不多贅述了，我們以示例1為例，當前地上有3個物體，背包的體積只有5。物體1的體積是2，價值為10，物體2的體積是4，價值為5，物體3的體積是1，價值為4。（1）要求我們在不超過背包體積的情況下，裝下的物體的最大價值。（2）要求我們求出當背包正好裝滿時，能裝下的最大價值。

對于問題1，由于我們要盡可能的追求最大價值，因此只要背包能裝下東西就一定要裝下：示例1有下面兩種方案。選擇價值最大的方案

對于問題2，只有一種方案能讓背包裝滿，因此雖然價值不是最大的，但是依舊是最終答案

題目1算法原理

對于問題1，我們要抽象出背包問題的兩個重要屬性。1、可挑選的物品有限制，2、要求挑選出物品的最大價值，那么我們的狀態表示就要涵蓋這兩個方面。

我們將物品進行從1開始編號，如下

我們規定，dp[i][j]表示：在[1,i]號物品中進行挑選，物體的總體積不超過j的最大價值。為什么要假設是這個狀態表示？首先根據上面的分析，我們知道狀態表示要涵蓋對選取物體的限制，同時也要確定最大價值，其二則是根據題目要求，題目要求我們在n個物品中挑選體積不超過背包體積的最大價值，而正好我們的狀態表示符合這個要求。

那么如何判斷我們的狀態表示正確與否呢？我們可以先嘗試用這個狀態表示來推導一下狀態轉移方程，如果狀態轉移方程推導的不是很順利。那么就要嘗試更換一個狀態表示了。

回到dp[i][j]的狀態表示。在[1,i]中挑選物品，對于每一個i，可以將所有的可能的情況分成兩種，一種是不將物體i裝進背包的情況，一種是將物體i裝進背包的情況。

我們根據這兩個情況推導狀態專題方程。

如果我們選擇不將i裝入背包，那么此時我們就要在剩下的物品中，挑選總體積不超過j的多個物品，但是我們由于我們的dp[i][j]需要求的是最大值，那么也就說明，在剩下的物品中挑選總體積不超過j的情況，也必須是最大價值，即dp[i-1][j]。那么此時dp[i][j]=dp[i-1][j]。

如果我們將第i個物體放入背包，那么為了追求最大價值，我們需要在[1,i-1]當中挑選剩下的物品，但是，由于此時背包當中已經放入一個i了，那么剩下的可容納體積則是j-v[i]。因此該情況下的dp[i][j]=dp[i-1][j-v[i]]+w[i]。由于我們要求出的是最大值，因此狀態轉移方程如下：
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])。但是要注意下標的問題，j-v[i]是可能小于0的，因此只有j-v[i]<=0的時候，我們就認為dp[i-1][j-v[i]]+w[i]的值為0。

接下來就是初始化問題，由于狀態轉移方程涉及i-1這個操作，因此我們不能讓i=0，因此我們要對其進行初始化。

如果i0,j0,則說明在0個物體當中挑選體積不超過0的最大價值，由于此時沒有物體可選，因此背包價值為0，即dp[0][0]=0
如果i=0,j>0,則說明在0個物體當中挑選體積不超過j的最大價值，同樣的沒有物體可選，因此背包價值為0.dp[0][j]=0

由于題目中會輸入n個物體，因此v[i]和w[i]的下標是[0,n-1]范圍內，但是我們的dp表的返回值是dp[n][V]。即表示在n個物體當中組合出體積不超過V的最大價值。所以dp表的是一個(n+1)*（V+1）大小的數組。此時我們要注意dp表的狀態轉移方程與v[i]和w[i]的下標映射關系。即：dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])

題目1題解代碼。

int main() {int n,V;cin>>n>>V;vector<int> v(n);//物體體積表vector<int> w(n);//物體價格表for(int i=0;i<n;i++) cin>>v[i]>>w[i];vector<vector<int>> dp(n+1,vector<int>(V+1));for(int i=1;i<n+1;i++){for(int j=0;j<V+1;j++){dp[i][j]=dp[i-1][j];//不選i的情況下的最大值if(j-v[i-1]>=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);//選i情況下的最大值，前提是合法}}cout<<dp[n][V]<<endl;
}

問題2算法原理

由于問題2要求是在裝滿背包的情況下，裝取物品的最大價值。 那么我們就可以將狀態表示修改一下：dp[i][j]表示，在前i個物品當中進行挑選，當挑選的物品恰好總體積為J時，背包的最大價值。

那么我們可以開始推導狀態轉移方程了，對于任意i，我們可以將所有的可能的枚舉情況，分成兩種，一種是選擇i的情況，一種是不選i的情況。因此我們需要推導出這兩種情況下dp[i][j]的最大值。

對于不選i的情況，此時我們可以在剩下的i-1個物品中挑選恰好體積等于j的最大值，那么這段描述不是符合dp[i-1][j]的狀態表示？因此狀態轉移方程為：dp[i-1][j]。

對于選i的情況，此時由于物品i已經被選進背包了，此時背包容量只剩j-v[i]。物品還剩下i-1個可以挑選，因此我們需要在剩下的i-1個物品進行挑選，使其總體積恰好為j-v[i]的情況下的最大價值，那么這段描述的狀態表示就是dp[i-1][j-v[i]]。由于物品i已經被選上了，因此選i的背包價值為： dp[i][j]=dp[j-v[i]]+w[i]。

但是有一個問題出現了，如果dp[i-1][j-v[i]]有沒有可能不存在？當然是有可能的，因為剩下的i-1個物體很有可能怎么湊，都湊不出j-v[i]這個體積，那么相應的，dp[i][j]的值也就不存在了。那么我們就要思考一個問題了，對于非法的狀態表示（即無法湊滿總體積為j的物品）,該用什么值來表示呢？有人說既然背包沒有東西，那不就是沒有價值。因此用0來表示。但是我們再思考一下，0這個值一定是非法的嗎？在前面討論初始化的時候，博主是不是說過，當i0時，j0時，此時有0個物體可挑選，需要讓挑選物品的總體積恰好為0。這個狀態明明是合法的，而且由于此時什么也沒挑，因此背包的最大價值為0，因此0不是非法狀態下的取值。我們可以使用-1來表示非法狀態下的表示。

因此狀態轉移方程為：dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])(dp[i-1][j-v[i]]合法的情況下(不為-1))。

接下來就是初始化的問題，i0時，j0時合法，因此背包價值為0，dp[0][0]=0.當i==0，j>0時，此時無法湊成總體積恰好為j的情況，因此是非法的情況，即dp[0][j]=-1。那么最后一個細節就是體積表和價值表與dp表之間的映射問題了。

問題2題解代碼

#include <iostream>
#include <vector>
using namespace std;int main() {int n,V;cin>>n>>V;vector<int> v(n);//物體體積表vector<int> w(n);//物體價格表for(int i=0;i<n;i++) cin>>v[i]>>w[i];vector<vector<int>> dp(n+1,vector<int>(V+1));for(int i=1;i<n+1;i++){for(int j=0;j<V+1;j++){dp[i][j]=dp[i-1][j];//不選i的情況下的最大值if(j-v[i-1]>=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);//選i情況下的最大值，前提是合法}}cout<<dp[n][V]<<endl;//問題1的結果dp.resize(n+1,vector<int>(V+1));//重新復用一下dp表for(int j=1;j<V+1;j++) dp[0][j]=-1;for(int i=1;i<n+1;i++){for(int j=0;j<V+1;j++){dp[i][j]=dp[i-1][j];//選i且合法的情況if(j-v[i-1]>=0&&dp[i-1][j-v[i-1]]!=-1) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);//}}cout<<(dp[n][V]==-1?0:dp[n][V])<<endl;//問題2的結果
}

01背包問題的滾動數組優化

根據狀態轉移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1]);對于任意一個位置的dp[i][j]，其取值返回都只在上一行當中。

（寫到這里博主的截圖工具有點用不了了，但是又是因為在學校機房寫的，因此不想關機重寫hh，那就用截圖鍵湊合看吧）

我們可以看到實際上只需要兩行的數組，只要下面一行填完了，就讓下面一行去作為上面一行繼續更新。那么就可以實現空間優化。

實際上這個工作只需要一行數組就能完成。如下：

由于我們對于任意一個dp[i][j]，我們都只會用到上一行，以及上一行當中左邊的某一個值。因此如果我們之開一行數組，然后從右往左遍歷dp。這樣dp表就可以僅使用一維的情況下，完成整個過程，節省了空間開銷。

代碼如下：

#include <iostream>
#include <vector>
using namespace std;int main() {int n,V;cin>>n>>V;vector<int> v(n);//物體體積表vector<int> w(n);//物體價格表for(int i=0;i<n;i++) cin>>v[i]>>w[i];vector<int> dp(V+1);//只需要一行dpfor(int i=1;i<n+1;i++){//注意雖然dp表只有一行，但是狀態轉移方程并沒有改變，因此i不能刪除for(int j=V;j>=v[i-1];j--){dp[j]=max(dp[j],dp[j-v[i-1]]+w[i-1]);//選i情況下的最大值，前提是合法}}cout<<dp[V]<<endl;//問題1的結果dp.resize(V+1);//重新復用一下dp表for(int j=1;j<V+1;j++) dp[j]=-1;for(int i=1;i<n+1;i++){for(int j=V;j>=v[i-1];j--){//選i且合法的情況if(dp[j-v[i-1]]!=-1) dp[j]=max(dp[j],dp[j-v[i-1]]+w[i-1]);//}}cout<<(dp[V]==-1?0:dp[V])<<endl;//問題2的結果
}