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

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

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

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

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

1、01背包問(wèn)題

2、完全背包問(wèn)題

3、多重背包問(wèn)題

其中最簡(jiǎn)單的背包問(wèn)題為01背包問(wèn)題，下面為維基百科里的一張圖：

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

問(wèn)題可以描述為：

1、問(wèn)題描述

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

如果用暴力解法

2、背包問(wèn)題用貪心算法無(wú)法解決例如，下圖，如果有id為：0，1，2的3個(gè)物品，其重量weight[]為：1，2，3，其價(jià)值value[]為：6，10，12。通過(guò)公式v/w，得到其價(jià)值為：6，5，4，要放入到空間為5的背包里。如果先放價(jià)值高的，就是放id為0，重量為1，價(jià)值為6的；再放id為1，重量為2，價(jià)值為10的。這時(shí)占用的重量就為1+2=3，還剩下5-3=2的重量，所以此時(shí)已經(jīng)不能再放id為0的物品。所以總的價(jià)值就是6+10=16。如下圖所示

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

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

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

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

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

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

i和c的含義：表示為考慮將前i個(gè)物品放進(jìn)容量為c的背包

3、問(wèn)題化解為求2個(gè)問(wèn)題的最大值這時(shí)要求解的問(wèn)題可以化解為求下面2個(gè)問(wèn)題的最大值

（1）第i個(gè)物品不放進(jìn)背包里，這時(shí)的價(jià)值就是i-1時(shí)的價(jià)值：F(i-1,c)

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

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

千言萬(wàn)語(yǔ)還不如直接看代碼來(lái)得實(shí)際。下面看2種方式的實(shí)現(xiàn)。

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

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

/// 背包問(wèn)題 /// 記憶化搜索 /// 時(shí)間復(fù)雜度: O(n * C) 其中n為物品個(gè)數(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個(gè)物品放進(jìn)容量為C的背包，使得價(jià)值最大。 // 要求的問(wèn)題就是最后一個(gè)n-1, 容量為C return bestValue(w, v, n - 1, C); } // 用 [0...index]的物品,填充容積為c的背包的最大價(jià)值 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、動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃的實(shí)現(xiàn)是自底向上實(shí)現(xiàn)，和記憶化的方向是相反的，但其記憶數(shù)組的定義是一樣的。

/// 背包問(wèn)題 /// 動(dòng)態(tài)規(guī)劃 /// 時(shí)間復(fù)雜度: O(n * C) 其中n為物品個(gè)數(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) { } }三、示例分析用上面的例子演示整個(gè)過(guò)程的示例分析：

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

下面表格的藍(lán)色行0，1，2，3，4，5表示容量數(shù)量的變化從0到5；藍(lán)色列0，1，2為3個(gè)物品。表格表達(dá)的含義為：0，1，2的3個(gè)物品，其容量從0變化到5，各個(gè)情況的最大價(jià)值。

表格里的數(shù)值表示為價(jià)值，表示在前i件（包括i件）物品中選擇若干件放在承重為 j 的背包中，可以取得的最大價(jià)值。

1、剛開(kāi)始都為空

2、把id為0的物品放到表格里，在容量遞增時(shí)的各個(gè)價(jià)值如下。容量為0時(shí)價(jià)值都是為0，容量為1時(shí)價(jià)值為6，因?yàn)槲锲穒d為0的重量就是1，所以無(wú)論容量怎么遞增其價(jià)值都是為6

3、當(dāng)id為1的物品放入去時(shí)，因?yàn)樗闹亓繛?，所以當(dāng)容量為1時(shí)，它是不能放進(jìn)去的，此時(shí)價(jià)值最大的依然為上一次的物品的價(jià)值，即為6

4、當(dāng)id為1的物品放入去時(shí)，當(dāng)其容量到達(dá)為2時(shí)，這時(shí)物品id為1的就可以放進(jìn)去了，但是根據(jù)v(i)+F(i-1, c-w(i) )，c-w(i) =》2-2=0 ，即id為0的物品就不能放到背包里了，此時(shí)的價(jià)值為10

5、繼續(xù)往后走我們看當(dāng)容量增加到3時(shí)，可以放下id為0和id為1的物品，這時(shí)物品的價(jià)值為它們的和10+6=16，符合v(i)+F(i-1, c-w(i) )，c-w(i) ，比原來(lái)的6大，所以此時(shí)為16

增加到4，原理一樣

6、當(dāng)物品id變化為2，到達(dá)容量為3的時(shí)候，因?yàn)槲锲愤€是放不進(jìn)去，還是前一個(gè)狀態(tài)id為0和id為1的2個(gè)物品，價(jià)值為16

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

8、到達(dá)最后一個(gè)的時(shí)候，容量達(dá)到了5，取的為10+12=22