在前面文章的例子裡面講解了許多動态規劃的問題，說明了哪些問題可以用動态規劃來解決以降低時間複雜度。動态規劃裡有許多經典的問題，其中0-1背包問題是最基礎的問題，下面将進行講解什麼是0-1背包問題及其講解。

關于背包問題，可以參考如下：

根據維基百科，背包問題（Knapsack problem）是一種組合優化的NP完全（NP-Complete，NPC）問題。

問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量内，我們如何選擇，才能使得物品的總價格最高。

NPC問題是沒有多項式時間複雜度的解法的，但是利用動态規劃，我們可以以僞多項式時間複雜度求解背包問題。一般來講，背包問題有以下幾種分類：

1、01背包問題

2、完全背包問題

3、多重背包問題

其中最簡單的背包問題為01背包問題，下面為維基百科裡的一張圖：

怎麼把價值為4美元12kg，價值為2美元2kg，價值為1美元1kg，價值為10美元4kg，價值為2美元1kg的物品進入隻有15kg的背包，使其價值最大。

問題可以描述為：

01背包問題（01 knapsack problem）：一共有n件物品，第i件物品的重量為w[i]，價值為v[i]。在總重量不超過背包承載上限C的情況下，能夠裝入背包的最大價值是多少？

如果用暴力解法

例如，下圖，如果有id為：0，1，2的3個物品，其重量weight[]為：1，2，3，其價值value[]為：6，10，12。通過公式v/w，得到其價值為：6，5，4，要放入到空間為5的背包裡。如果先放價值高的，就是放id為0，重量為1，價值為6的；再放id為1，重量為2，價值為10的。這時占用的重量就為1 2=3，還剩下5-3=2的重量，所以此時已經不能再放id為0的物品。所以總的價值就是6 10=16。如下圖所示

然而，我們明顯知道真正的最優方法為如下的方式，放id為1和id為2的物品，其重量為5，價值可以達到10 12=22。

因此解決背包這種問題貪心算法是不适用的，還是要用到動态規劃來解決。

由上一篇文章我們得知要解決動态規劃問題就是要定義好記憶化搜索數組和函數及函數的實現。我們先實現一下其代碼過程，後面再分析代碼實現具體的過程。

memo[i,j]表示在前i件（包括i件）物品中選擇若幹件放在承重為 j 的背包中，可以取得的最大價值。

狀态定義（要求的結果）：F(n,C) 考慮将n個物品放進容量為C的背包，使得價值最大。本文的值就為memo[n - 1][C]

狀态轉移方程：F(i,c) 考慮将前i個物品放進容量為c的背包，得到的最大價值

i和c的含義：表示為考慮将前i個物品放進容量為c的背包

這時要求解的問題可以化解為求下面2個問題的最大值

（1）第i個物品不放進背包裡，這時的價值就是i-1時的價值：F(i-1,c)

（2）如果第i個可以放入來，且不超過容量C，這是的價值為第i個物品的價值加上前面i-1的價值，注意這時i-1的重量為c-w(i)：v(i) F(i-1, c-w(i) )

即問題變為求解（1）和（2）的最大值就可以。如下：

千言萬語還不如直接看代碼來得實際。下面看2種方式的實現。

在看代碼之前大家記得看上面記憶化搜索數組的定義，狀态定義與狀态轉移方程。不要一頭鑽進代碼裡，要先理解函數定義。

private int[][] memo; 是一個二維數組，表示在前i件（包括i件）物品中選擇若幹件物品放在承重為 j 的背包中，可以取得的最大價值。

/// 背包問題 /// 記憶化搜索 /// 時間複雜度: O(n * C) 其中n為物品個數; C為背包容積 /// 空間複雜度: O(n * C) public class Solution1 { private int[][] memo; public int knapsack01(int[] w, int[] v, int C){ if(w == null || v == null || w.length != v.length) throw new IllegalArgumentException("Invalid w or v"); if(C < 0) throw new IllegalArgumentException("C must be greater or equal to zero."); int n = w.length; if(n == 0 || C == 0) return 0; memo = new int[n][C 1]; // 初始化數組 for(int i = 0; i < n; i ) for(int j = 0; j <= C; j ) memo[i][j] = -1; // 根據上面=》狀态定義（要求的結果）：F(n,C)考慮将n個物品放進容量為C的背包，使得價值最大。 // 要求的問題就是最後一個n-1, 容量為C return bestValue(w, v, n - 1, C); } // 用 [0...index]的物品,填充容積為c的背包的最大價值 private int bestValue(int[] w, int[] v, int index, int c){ if(c <= 0 || index < 0) return 0; if(memo[index][c] != -1) return memo[index][c]; int res = bestValue(w, v, index-1, c); if(c >= w[index]) res = Math.max(res, v[index] bestValue(w, v, index - 1, c - w[index])); return memo[index][c] = res; } public static void main(String[] args) { } }

動态規劃的實現是自底向上實現，和記憶化的方向是相反的，但其記憶數組的定義是一樣的。

/// 背包問題 /// 動态規劃 /// 時間複雜度: O(n * C) 其中n為物品個數; C為背包容積 /// 空間複雜度: O(n * C) public class Solution2 { public int knapsack01(int[] w, int[] v, int C){ if(w == null || v == null || w.length != v.length) throw new IllegalArgumentException("Invalid w or v"); if(C < 0) throw new IllegalArgumentException("C must be greater or equal to zero."); int n = w.length; if(n == 0 || C == 0) return 0; int[][] memo = new int[n][C 1]; for(int j = 0 ; j <= C ; j ) memo[0][j] = (j >= w[0] ? v[0] : 0 ); for(int i = 1 ; i < n ; i ) for(int j = 0 ; j <= C ; j ){ memo[i][j] = memo[i-1][j]; if(j >= w[i]) memo[i][j] = Math.max(memo[i][j], v[i] memo[i - 1][j - w[i]]); } return memo[n - 1][C]; } public static void main(String[] args) { } }

用上面的例子演示整個過程的示例分析：

3個物品，容量為5。其id為：0，1，2的3個物品，其重量weight[]為：1，2，3，其價值value[]為：6，10，12；放入到空間為5的背包裡。

下面表格的藍色行0，1，2，3，4，5表示容量數量的變化從0到5；藍色列0，1，2為3個物品。表格表達的含義為：0，1，2的3個物品，其容量從0變化到5，各個情況的最大價值。

表格裡的數值表示為價值，表示在前i件（包括i件）物品中選擇若幹件放在承重為 j 的背包中，可以取得的最大價值。

1、剛開始都為空

2、把id為0的物品放到表格裡，在容量遞增時的各個價值如下。容量為0時價值都是為0，容量為1時價值為6，因為物品id為0的重量就是1，所以無論容量怎麼遞增其價值都是為6

3、當id為1的物品放入去時，因為它的重量為2，所以當容量為1時，它是不能放進去的，此時價值最大的依然為上一次的物品的價值，即為6

4、當id為1的物品放入去時，當其容量到達為2時，這時物品id為1的就可以放進去了，但是根據v(i) F(i-1, c-w(i) )，c-w(i) =》2-2=0 ，即id為0的物品就不能放到背包裡了，此時的價值為10

5、繼續往後走我們看當容量增加到3時，可以放下id為0和id為1的物品，這時物品的價值為它們的和10 6=16，符合v(i) F(i-1, c-w(i) )，c-w(i) ，比原來的6大，所以此時為16

增加到4，原理一樣

6、當物品id變化為2，到達容量為3的時候，因為物品還是放不進去，還是前一個狀态id為0和id為1的2個物品，價值為16

7、當物品id為2，其容量到達4的時候，這時可以放進去了，根據v(i) F(i-1, c-w(i) )，12 6與16比較大小，取18

8、到達最後一個的時候，容量達到了5，取的為10 12=22

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!