0/1背包問題

0/1背包的問題在于每個物品只有1件，每件物品只能選擇放或者不放，于是就有了動態規劃的解法：

for(int i = 1; i <= m; ++i) {for(int j = 1; j <=n j++) {f[i][j]=max(f[i?1][j],f[i?1][j?c[i]]+w[i])}}

f[i][j] 表示 前i個物品放到容量為j的背包的最大價值，直接聊聊優化空間的事情，這里注意表達式，我們要優化的就是表達式中的一維數組，也就是i所在的坐標，從表達式可以看到這里只要保證求解i個物品時，i-1個物品的狀態沒變就行，怎么讓這個狀態不變呢？那就只能是更新物品時逆序更新，這樣每一輪的更新物品后，

?for (int i = 1; i <= n; i++)for (int j = V; j >= 0; j--)f[j] = max(f[j], f[j - c[i]] + w[i]);

上述代碼的意思就是：容量為j的袋子可以放的最多價值的物品，當j從V到0的時候，放第一個物品，每個容量可以最多價值f(j)，最后不停的增加物品，來更新f(j)的值。

完全背包問題

題目：有N 種物品和一個容量為V的背包，每種物品都有無限件可用。第i 種物品的費用是c [ i ] ，價值是w [ i ] 。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

那么還是回到二維數組的轉移法方程：

f[i][j]=max(f[i?1][j?k?c[i]]+k?w[i]) ∣0≤k?c[i]≤j

這說明01背包問題的方程的確是很重要，可以推及其它類型的背包問題。我們繼續改進這個復雜度。這里唯一的特點就是物品可以無限取，所以我們將容量為V的背包除以每一個物品的重量，這樣可以得到該物品最多可以裝進背包的個數，然后這個問題就變為了0/1背包問題，只不過物品數目增加了，然后就利用0/1背包的公式來求解，

?for (int i = 1; i <= n; i++)for (int j = V; j >= 0; j--)f[j] = max(f[j], f[j - c[i]] + w[i]);

公式沒變，物品數量變多。

關于二進制提高速度

其實主要思想是減少相同物品的數量，比如背包容量為10，有一個物品中重量為1，價值為2，可以選擇這個物品10個，得到價值20，如果把這個物品擴展到10個，形成0/1背包問題，那么物品數量有點多，那么有沒有減少物品數量的辦法，不需要10個相同的物品呢？這時候就采取二進制方法，利用二進制的特點，減少物品數量，比如111這個二進制數，表示的是7，第一個1表示4，第二個1表示2，第三個1表示1，那么由這三個物品，1、2、4就可以組合成0~7的所有數字，也就是需要1、2、4、8就可以滿足10個物品的組合，根本不需要10個重量為1、價值為2的物品，只需要4個物品，分別是：

• 重量為1，價值為2
• 重量為2，價值為4
• 重量為4，價值為8
• 重量為8，價值為16

這樣也提高了速度。

參考博客

背包九講——全篇詳細理解與代碼實現

總結

以上是生活随笔為你收集整理的背包问题九讲的总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。