來源頭條作者:小夸大夸在前面文章的例子里面講解了許多動態(tài)規(guī)劃的問題，說明了哪些問題可以用動態(tài)規(guī)劃來解決以降低時間復(fù)雜度。動態(tài)規(guī)劃里有許多經(jīng)典的問題，其中0-1背包問題是最基礎(chǔ)的問題，下面將進行講解什么是0-1背包問題及其講解。

一、0-1背包問題關(guān)于背包問題，可以參考如下：

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

問題可以描述為：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價格最高。

NPC問題是沒有多項式時間復(fù)雜度的解法的，但是利用動態(tài)規(guī)劃，我們可以以偽多項式時間復(fù)雜度求解背包問題。一般來講，背包問題有以下幾種分類：

1、01背包問題

2、完全背包問題

3、多重背包問題

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

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

問題可以描述為：

1、問題描述

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

如果用暴力解法

2、背包問題用貪心算法無法解決例如，下圖，如果有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的重量，所以此時已經(jīng)不能再放id為0的物品。所以總的價值就是6+10=16。如下圖所示

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

因此解決背包這種問題貪心算法是不適用的，還是要用到動態(tài)規(guī)劃來解決。

二、狀態(tài)定義與狀態(tài)轉(zhuǎn)移方程的確定由上一篇文章我們得知要解決動態(tài)規(guī)劃問題就是要定義好記憶化搜索數(shù)組和函數(shù)及函數(shù)的實現(xiàn)。我們先實現(xiàn)一下其代碼過程，后面再分析代碼實現(xiàn)具體的過程。

1、記憶化搜索數(shù)組的定義memo[i,j]表示在前i件（包括i件）物品中選擇若干件放在承重為 j 的背包中，可以取得的最大價值。

2、狀態(tài)定義與狀態(tài)轉(zhuǎn)移方程狀態(tài)定義（要求的結(jié)果）：F(n,C) 考慮將n個物品放進容量為C的背包，使得價值最大。本文的值就為memo[n - 1][C]

狀態(tài)轉(zhuǎn)移方程：F(i,c) 考慮將前i個物品放進容量為c的背包，得到的最大價值

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

3、問題化解為求2個問題的最大值這時要求解的問題可以化解為求下面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) )

即問題變?yōu)榍蠼猓?）和（2）的最大值就可以。如下：

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

4、記憶化搜索實現(xiàn)在看代碼之前大家記得看上面記憶化搜索數(shù)組的定義，狀態(tài)定義與狀態(tài)轉(zhuǎn)移方程。不要一頭鉆進代碼里，要先理解函數(shù)定義。

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

/// 背包問題 /// 記憶化搜索 /// 時間復(fù)雜度: O(n * C) 其中n為物品個數(shù); C為背包容積 /// 空間復(fù)雜度: 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]; // 初始化數(shù)組 for(int i = 0; i< n; i ++) for(int j = 0; j<= C; j ++) memo[i][j] = -1; // 根據(jù)上面=》狀態(tài)定義（要求的結(jié)果）：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) { } }5、動態(tài)規(guī)劃實現(xiàn)動態(tài)規(guī)劃的實現(xiàn)是自底向上實現(xiàn)，和記憶化的方向是相反的，但其記憶數(shù)組的定義是一樣的。

/// 背包問題 /// 動態(tài)規(guī)劃 /// 時間復(fù)雜度: O(n * C) 其中n為物品個數(shù); C為背包容積 /// 空間復(fù)雜度: 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表示容量數(shù)量的變化從0到5；藍色列0，1，2為3個物品。表格表達的含義為：0，1，2的3個物品，其容量從0變化到5，各個情況的最大價值。

表格里的數(shù)值表示為價值，表示在前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的就可以放進去了，但是根據(jù)v(i)+F(i-1, c-w(i) )，c-w(i) =》2-2=0 ，即id為0的物品就不能放到背包里了，此時的價值為10

5、繼續(xù)往后走我們看當容量增加到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的時候，因為物品還是放不進去，還是前一個狀態(tài)id為0和id為1的2個物品，價值為16

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

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