????????本文章是對于完全背包 一些題型(如題目所示，組合、排列和最小值類型)的總結和理解，依次記錄一下，方便回顧與復習。

? ? ? ? 本文章是基于個人所總結 實現的，但在其中遇到了一些疑惑與困難，所以總結一篇與完全背包相關的問題。

? ? ? ? 題型分為 完全背包 求組合問題 、 求排列問題、 求最小值問題.

但這一切都是基于完全背包，我們先來介紹一下什么是完全背包。

目錄

完全背包問題

二維dp

?二維優化

一維dp(滾動數組)

完全背包組合和排列問題

---

完全背包問題

????????有N件物品和一個最多能背重量為W的背包。第i件物品的重量是weight[i]，其價值為value[i] 。每件物品都有無限個（也就是可以放入背包多次），求解將哪些物品裝入背包里物品價值總和最大。(即如何在有限的空間中 盡可能放到整體價值最高).

????????完全背包和01背包問題唯一不同的地方就是，完全背包每種物品有無限件；而01背包每個物品只有一件。

? ? ? ? 在這里我認為對你對01背包 已經有一定的了解，便不再深入贅述。如果不了解01背包，最好先了解之后再繼續閱讀。

二維dp

這是 01背包的核心代碼

     // 二維數組vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));// 初始化for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];}// weight數組的大小 就是物品個數for(int i = 1; i < weight.size(); i++) { // 遍歷物品for(int j = 0; j <= bagweight; j++) { // 遍歷背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j];//如果當前背包容量小于物品體積，則直接不做選擇else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);//如果大于物品體積，則取 選擇當前物品 和 不選擇當前物品 的最大值}}

01背包是每次從中選取一個物品 一次，即如果作選取決策的話，當前重量j 只用減去一個weight[i],所以選取后的重量是dp[i-1][j-weight[i]].

注意我下面所說的當前容量，而沒有說背包總容量。因為我們是從小到大遍歷的背包容量。

而完全背包是 可以選取一個物品 多次(k>=0)，即如果作選取決策的話，當前重量j 要減去 k個weight[i],具體多少取決于當前背包容量的大小。所以我們for循環 k從0開始遍歷，直至 大于當前背包容量停止。而我們也要做出抉擇，即選出0-k次中最大的值，如下：

max (dp[i-1][j-weight[i] * k] + value[i]*k)

如果作不選取 決策的話，那么當前的值就不變化，繼承上一次的值。即dp[i][j] = dp[i-1][j];

?所以現在狀態轉移方程為：

dp[i][j] = max {?max (dp[i-1][j-weight[i] * k] + value[i]*k), dp[i-1][j] }. 其中(1 <= k <= j/weight[i]

代碼如下：

    //n代表物品的數量，v代表背包的容量，weight[i]代表第i個物品的體積，value[i]是第i個物品的價值vector<vector<int>> dp(N+1,vector<int>(N+1,0));//遍歷背包物品for(int i = 1; i <= n; i++){  //遍歷背包容量for(int j = 1; j <= v; j++){//每次選取k件 物品i ，如果容量大于 當前容量j，則停止for(int k = 1; k * weight[i] <= j; k++){//這句代碼相當于max (dp[i-1][j-weight[i] * k] + value[i]*k),而由于k每次在同一行，所以每次和dp[i][j]進行比較。當然這里寫max(dp[i-1],...)也沒關系，因為最后都是取的 dp[i-1][j-k*weight[i]]+value[i]*k)的最大值。選dp[i-1][j]相當于每次都和第一次比較，而選dp[i][j]相當于每次都和上一次的進行比較，所以dp[i][j]最后一定是最大值dp[i][j] = max(dp[i][j],dp[i-1][j-k*weight[i]]+value[i]*k);}//dp[i][j] = max(dp[i-1][j],dp[i][j]); //這句代碼其實不用加，因為上面第一次k一定等于0，//所以相當于第一次已經比較了。這里寫只是為了更好的顯示上面的思路}}return dp[n-1][v];

?二維優化

上面我們用了三重for循環，時間復雜度太高了，我們有沒有辦法把它轉化成二維的呢？

記得上面剛說的這個狀態轉移方程：

一.dp[i][j] = max {?max (dp[i-1][j-weight[i] * k] + value[i]*k), dp[i-1][j] }.

其中(1 <= k <= j/weight[i]）

我們看到k的取值最小值為1，那我們不妨先把這 一個物品放進去

得到：

二.dp[i][j] = max {max(dp[i-1][j-weight[i]*k -weight[i]]+value[i]*k +value[i]),dp[i-1][j]);

此時k的取值范圍為：(0?<= k <= j/weight[i]-1)

對于式子一，我們完全可以可以把式子簡化為如下：

三.dp[i][j] = max(dp[i-1][j-weight[i] * k] + value[i]*k),其中

其中(0?<= k <= j/weight[i]）

這是如何做到的呢？我們發現式子一 k的最小值是1，那么當我們讓k=0時，發現dp[i-1][j-weight[i] * k] + value[i]*k)就是dp[i-1][j].所以我們完全可以合并這兩個！最后只留下一個max，只不過k的最小值由1變成了0.

當j=j-weight[i]時，我們將其帶入到式子三：

四.dp[i][j-weight[i]] = max(dp[i-1][j-weight[i] - weight[i]*k] + value[i]*k);其中：

(0?<= k <= j/weight[i]-1)

此時我們再用式子二對比式子四：

二.dp[i][j] = max {max(dp[i-1][j-weight[i]*k -weight[i]]+value[i]*k +value[i]),dp[i-1][j]);

四.dp[i][j-weight[i]] = max(dp[i-1][j- weight[i]*k -weight[i]] + value[i]*k);

?可以發現它們是畫圈的這一部分完全等價的！范圍也是一樣的。我們我們把式子四 替換到式子二中：

即dp[i][j] = max(dp[i][j-weight[i]]+value[i]，dp[i-1][j]).

這就是我們最終推導出的公式！！！

所以我們再也不需要寫那三重循環了，直接二維循環就可以，如下：

    vector<vector<int>> dp(N+1,vector<int>(N+1,0));//遍歷背包物品for(int i = 1; i <= n; i++){  //遍歷背包容量for(int j = 0; j <= v; j++){//如果選擇的話if(j >= weight[i])dp[i][j] = max(dp[i][j-weight[i]]+value[i],dp[i-1][j]);//如果不選擇elsedp[i][j] = dp[i-1][j];}}

一維dp(滾動數組)

和01背包問題問題類似，我們同樣可以轉化為把? 二維數組轉化為一維數組，因為它們都只依賴于上一行的狀態。

因此我們由

dp[i][j] = max(dp[i][j-weight[i]]+value[i],dp[i-1][j]);

可以轉化為一維dp數組：

dp[j] = max(dp[j-weight[i]]+value[i],dp[j]);

修改完畢后，代碼如下:

    vector<int> dp(N+1,0);for(int i = 1; i <= n; i++){for(int j = weight[i]; j <= v; j++){dp[j] = max(dp[j-weight[i]]+value[i],dp[j]);}}return dp[v];

完全背包組合和排列問題

先說結論：

利用背包 求組合數 是外層遍歷物品，內層遍歷 物品容量

利用背包求 排列數?是 想外層先遍歷物品的容量，內層再遍歷 物品.

組合 不強調順序，而排列強調順序

為什么是這樣呢？

假設你有價值為1元 和 2元的硬幣，數量分別有無限個，那么讓你湊成價值為5元的方案有多少種？

這個里面，有這樣的兩種方案：1 2 2? ? 2? 1 2??

如果是組合數，它們將會被視為一種組合，而如果是排列數，那么它們將是兩種不同的排列

具體來說：

假設你先遍歷的物品數量，那么你后面只能按照固定的順序遍歷了。

假設物品有 abc，那么你也只能按照abc這個順序來放入了. b根本沒機會放到a的前面，因為遍歷完a結束 才遍歷b的. 所以這樣是求組合數

相反的，假設你先遍歷的物品容量，再遍歷物品數量，這樣每個物品都有機會放入背包中，順序也不固定，假設裝a不合適，我可以裝b(ee，真沒別的意思)，隨著遍歷背包容量變大，說不定原來的a又適合裝入了，這樣就有了不同的順序了。

大家可以在leetcode上做下面的例題感受：

求組合數：
518.零錢兌換II

求排列數：

377.組合總和IV

到這里，關于完全背包的一些基礎相關的問題就講完了，實際上還需要大家看視頻或者做更多題感受到，可以看看題解中一些人發表的，他們發表的一種種類型及對應的題目可以非常好的鞏固自己！