完全背包和01背包，完全背包問題+01背包問題+分組背包+多重背包 總結

背包問題都涉及到動態規劃，利用dp進行更加優化的計算。

一、01背包

最基本的是01背包問題，題目一般類似：“在一定數目物品內，挑選總重量不超過一定數目的物品，其中每個物品只能選一次，求背包內物品價值的最大值或者最小值”，從名字就可以看出，要么選0個，要么選1個。

如果按照暴力的方法，時間復雜度會爆表，這里采用的是記憶化搜索的方式，加以DP。

首先，選一個二維數組dp，這個數組的含義是從前i個物品中選出總重量不超過j的物品時總價值的最大值，也就是說，對于數組中的任意一個元素dp[i][j]，其含義為在前i個物品中選出總重量不超過j的物品的最大值。

完全背包和01背包、定義好了數組，接下來就是找狀態轉移方程。最容易找到的就是最初的狀態，即dp[0][j]=0，在一個物品也不選的時候，不論總質量是多少，總價值肯定是0。接下來的狀態都是在這個基礎狀態上進行擴展。既然是放物品，那么肯定是物品一個一個遍歷，如果能放不下，其最大價值肯定還等于上一個狀態，也就是說當j<w[i]時，dp[i+1][j]=dp[i][j]，如果能放下，就需要比較是放下這個物品價值大還是不放價值大，當選擇放的時候，相當于在前i個物品中，空間為當前空間減去w[i+1]的情況再放這個物品，比較這個情況下價值的大小，即當j>=w[i]時，dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i])，這樣所有的狀態我們就找到了，即狀態轉移方程為：
dp[0][j]=0;
dp[i+1][j]=dp[i][j] i<w[i];
dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]) j>=w[i]

根據這個就可以寫出01背包最大值問題的模板了

for(int i=0;i<N;i++)
{for(int j=0;j<=wei;j++){if(j<w[i])dp[i+1][j]=dp[i][j];elsedp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);}
}
cout<<dp[N][wei]<<endl;

在這個的基礎上可以進行空間復雜度上的優化，不難發現每次對下一行的數據的更新都是取決于上一行的數據，所以并不一定需要開一個二維數組，一維數組就可以解決問題，我們關心的是最后一次外循環的值，中間過程我們并不需要知道，所以可以進行空間上的優化。

二維數組中我們進行的操作實際上就是在每個物品的基礎上，遍歷所有可能的背包空間，如果放得下去就比較放與不放對價值的影響，轉換為一維的時候，其實比較的就是在上一次操作的情況下，哪些還可以放得下這個物品，放得下的就進行比較。所以也就是要對w[i]到wei的范圍進行更新，轉換為代碼就是下面這個形式，轉換后dp數組的含義就變成了容量不超過j時的最大價值了，省略了前幾個物品這一項。

for(int i=0;i<N;i++)
{for(int j=wei;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+pri[i]);}
}
cout<<dp[wei]<<endl;

這里還需要注意，01背包的一維數組表示，更新的時候是逆序的，從代碼不難看出，對一個值的更新是基于這個值左邊的值進行更新的，如果是順序更新，那么在更新時一定會先更新左邊的值，從而使得后更新的值有可能基礎被更新過了，而逆序更新就可以避免這個問題。也可以這么說，因為01背包里面每個物品只能放一次，如果順序更新，那么假設狀態1已經放了一個物品了，那么基于狀態1的狀態2如果需要更新，那么不就變成了放兩個物品了么，這不就出錯了，所以應該需要逆序更新。

背包問題多個背包。這里舉例子都是舉的求最大值，這時需要把數組初始化為0，之后每一次都選取最大值即可。而當要求的是最小值時，則應該把數組初始化為很大的數，每次選取最小值。dp[N][wei]就是要求的最值。

二、完全背包

完全背包問題是在01背包問題上進行的延伸，01背包每次物品的數目只能是0或者1，而完全背包問題就脫離了這個限制，題目一般類似：“在一定數目物品內，挑選總重量不超過一定數目的物品，其中每個物品可以選多次，求背包內物品價值的最大值或者最小值”。這里就需要對上面的模板進行一定的修改了。

其實最笨的辦法是在01背包的基礎上再增加一層循環，用于記錄增加的件數

for(int i=0;i<N;i++)for(int j=0;j<=wei;j++)for(int k=1;k*wei[i]<=j;k++)dp[i+1][j]=max(dp[i][j],dp[i][j-k*wei[i]]+k*val[i]);
cout<<dp[N][wei]<<endl;

這種方法比較好懂，但是時間復雜度太大，需要進行優化，這里直接在01背包一維的基礎上進行一個優化，其實這兩種背包問題都是相通的，區別就在于01不可以放多個而完全背包可以放多個，在前面講一維化的地方說過，之所以逆序更新是防止放兩個的情況出現，那么這里完全背包就正好利用了這一點，把01背包的逆序更新換成順序更新，就可以解決放幾個的問題了，把所有還可以放的狀態都更新一遍，從左向右進行更新，如果前面的狀態就已經放得下一個了，那么基于這個狀態的另一個狀態還可以再放一個，所以就基于上個狀態繼續更新，因而是正序更新。具體表示為，當背包空間為j時，最大價值等于當前值和加上一個當前物品增加價值之后中更大的值。代碼如下

for(int i=0;i<N;i++)
{for(int j=w[i];j<=wei;j++){dp[j]=max(dp[j],dp[j-w[i]]+pri[i]);}
}
cout<<dp[wei]<<endl;

所以在記憶這兩種背包問題的時候，只需要理解好更新順序的問題，模板都是一樣的，只需要根據順序進行修改就好了。

三、分組背包

雙肩包背多重合適？分組背包問題是在01背包的基礎上又進行了延伸，01背包問題中每個物品要么選要么不選，在分組背包中，將一系列物品分成幾組，一次在一個小組中選擇一個或者不選，其實01背包是一種特殊情況下的分組背包，即每個組只有一個物品時的分組背包，我們依然可以沿用01背包的解題思路，只不過進行一下加工，這里直接取一維情況的dp數組，其實我們可以這樣認為，每個組既然只能選一個，我們可以先限定一個組別，之后在這個組別中，在總重量允許的條件下，看當前重量下是不是放得下這個組中的物品，放得下就選取價值的更大值。由于每次選擇的都是最大值而且是在這一個組中進行的操作，所以保證了一個組中只選擇了一個物品。由于分組背包是01背包延伸來的，所以依然是用逆序遍歷來實現一維數組的dp。

模板類似下面的代碼

for(int i=1;i<=N;i++)//第幾組for(int j=M;j>=1;j--)//允許的重量 for(int k=1;k<=這組的物品數;k++)//每組選物品 if(物品的重量<=j)dp[j]=max(dp[j],dp[j-物品的重量]+val[i][k]);

四、多重背包

多重背包問題的思路跟完全背包的思路非常類似，只是每種物品的取值是有限制的，因為每件物品的數量是有限制的。

多重背包一般采取轉化為01背包的方法，將每個物品按照2的冪次分成幾個物品，這樣就變成了01背包。把第i種物品換成n[i]件01背包中的物品。考慮二進制的思想，考慮把第i種物品換成若干件物品，使得原問題中第i種物品可取的每種策略——取0…n[i]件——均能等價于取若干件代換以后的物品。另外，取超過n[i]件的策略必不能出現。分成的這幾件物品的系數和為n[i]，表明不可能取多于n[i]件的第i種物品。這里一般都會用到二進制優化來減少時間復雜度，不然的話三層循環暴力確實有些吃不消。

模板如下

for(int j=1;j<=num[i];j*=2)//二進制優化 
{for(int k=n;k>=j*i;k--)//轉換為01背包，所以需要逆序更新 {if(dp[k-i*j]==1)dp[k]=1;}num[i]-=j;//剩余數量進行更新 
}
if(num[i]*i!=0)//對于不能進行二進制更新的部分直接當做一個物品處理 
{for(int k=n;k>=num[i]*i;k--)//對于剩下的部分應該也遍歷一遍 {if(dp[k-num[i]*i])dp[k]=1;}
}

五、總結

背包覺得重。總的來說，這四類背包問題的關系大致如下：
01背包：每個物品只有一個，要么選要么不選
完全背包：在01背包基礎上解除了只有一個的限制，每個物品隨便選
分組背包：嵌套的01背包，每組要么選一個要么不選，每組里面的物品只能選一個，也可以理解為最大數量為1的要么選要么不選
多重背包：在完全背包上加了數量的限制，依然是隨便選，但不能超過限制。

結題思路
01背包：逆序更新
完全背包：順序更新
這兩個是基礎，理解好原理就不難區分
分組背包：01背包的基礎上，再套一層循環來檢驗每一組的物品
多重背包：二進制優化后轉化為01背包