前言
背包問題隻是動态規劃問題下的一個分類，求解0-1背包問題的思路本質上與求解動态規劃的一般思路是一緻的，我們經常遇到新的題目做不出來，并不是因為沒有掌握動态規劃的思想，而有可能是因為沒有遇到這類具有顯著特征的題目，無法将一般動态規劃的解題思路應用在實戰中。
動态規劃的原理：
① 最優子結構性質：問題的最優解可以轉化為求子問題的最優解，也就是說問題的最優解可以從子問題的最優解中得出。
② 子問題重疊性質：問題的解由子問題的解組成，是以先構造子問題的解，才能求出最終問題的解。而求問題的解時，由于已經記錄子問題的解，是以不必重新求子問題的解，隻需取出來使用即可。
經典例題
有 N 件 物 品 和 一 個 容 量 為 V 的 背 包 。 放 入 第 i 件 物 品 耗 費 的 空 間 是 C i ， 得 到 的 價 值 是 W i 。 求 解 将 哪 些 物 品 裝 入 背 包 可 使 價 值 總 和 最 大 。 有N件物品和一個容量為V 的背包。放入第i件物品耗費的空間是Ci，得到 的價值是Wi。 \\求解将哪些物品裝入背包可使價值總和最大。 有N件物品和一個容量為V的背包。放入第i件物品耗費的空間是Ci，得到的價值是Wi。求解将哪些物品裝入背包可使價值總和最大。
例 ： N = 5 ， V = 10 例：N = 5，V=10 例：N=5，V=10
| 物品 | A | B | C | D | E |
|---|---|---|---|---|---|
| Wealth | 3 | 4 | 5 | 6 | 7 |
| Cost | 1 | 2 | 5 | 6 | 8 |
這是最基礎的0-1背包問題
先看下圖，是在求出問題的解後整個動态規劃表呈現的結果。下面就來看看這張表是如何一步步填上去并求出最終問題解的。
解題思路
① 确定子問題
求容量為V的背包裝入物品的價值總和最大，則考慮第i件物品是否放入背包，使得背包的價值保持最大。
② 确定狀态及數組
用一個二維數組F[i][j]表示前i件物品放入容量為j的背包中可以獲得的最大價值（注意此處的容量是背包的總容量，而不是背包的剩餘容量）
③ 确定邊界值
F[0][0…V] = 0：表示不管第0件物品放入任意容量的背包中其最大價值都是0，因為不存在第0件物品。
F[0…N][0] = 0：表示任意物品放入容量為0的背包中其最大價值都是0，因為容量為0的背包裝不下任何物品。
④ 确定狀态轉移方程
Ⅰ：若第i件物品無法放入容量為j的背包中
則 前 i 件 物 品 放 入 容 量 為 j 的 背 包 中 的 最 大 價 值 等 于 前 i − 1 件 物 品 放 入 容 量 為 j 的 背 包 中 的 最 大 價 值 ， 即 ： F [ i ] [ j ] = F [ i − 1 ] [ j ] \\則前i件物品放入容量為j的背包中的最大價值等于前i-1件物品放入容量為j的背包中的最大價值，\\即：F[i][j] = F[i-1][j] 則前i件物品放入容量為j的背包中的最大價值等于前i−1件物品放入容量為j的背包中的最大價值，即：F[i][j]=F[i−1][j]
Ⅱ：若第i件物品可以放入容量為j的背包中，則分兩種情況：
第 i 件 物 品 放 入 容 量 為 j 的 背 包 中 ， 得 到 前 i 件 物 品 的 最 大 價 值 ： F 1 [ i ] [ j ] = F [ i − 1 ] [ j − C i ] + W i 第 i 件 物 品 不 放 入 容 量 為 j 的 背 包 中 ， 得 到 前 i 件 物 品 的 最 大 價 值 ： F 2 [ i ] [ j ] = F [ i − 1 ] [ j ] 取 F 1 還 是 F 2 取 決 于 誰 的 價 值 更 大 ， 即 ： F [ i ] [ j ] = m a x ( F 1 [ i ] [ j ] , F 2 [ i ] [ j ] ) 第i件物品放入容量為j的背包中，得到前i件物品的最大價值：F_1[i][j] = F[i-1][j-C_i] + W_i \\第i件物品不放入容量為j的背包中，得到前i件物品的最大價值：F_2[i][j] = F[i-1][j] \\取F_1還是F_2取決于誰的價值更大，即：F[i][j] = max(F_1[i][j],\ F_2[i][j]) 第i件物品放入容量為j的背包中，得到前i件物品的最大價值：F1[i][j]=F[i−1][j−Ci]+Wi第i件物品不放入容量為j的背包中，得到前i件物品的最大價值：F2[i][j]=F[i−1][j]取F1還是F2取決于誰的價值更大，即：F[i][j]=max(F1[i][j], F2[i][j])
例：
第Ⅰ種情況：
當[i，j] = [2，1]時，物品B的耗費空間Cost=2，而背包的體積 j=1，很明顯物品B無法放入背包中，是以
F [ 2 ] [ 1 ] = F [ 1 ] [ 1 ] = 3 F[2][1] = F[1][1] = 3 F[2][1]=F[1][1]=3
第Ⅱ種情況：
當[i，j] = [2，3]時，物品B的耗費空間Cost = 2，而背包的體積 j=3，物品B可以放入背包中，是以
F [ 2 ] [ 3 ] = m a x ( F [ 1 ] [ 3 ] , F [ 1 ] [ 3 − 2 ] + 4 ) = m a x ( 3 , 3 + 4 ) = m a x ( 3 , 7 ) = 7 F[2][3] = max(F[1][3], F[1][3-2] + 4)=max(3,3+4)=max(3,7)=7 F[2][3]=max(F[1][3],F[1][3−2]+4)=max(3,3+4)=max(3,7)=7
作者在了解Ⅱ時有一個困惑：為什麼第i件物品可以放入容量為j的背包中還需要比較不放入的情況？
當 [ i ， j ] = [ 5 ， 9 ] 時 ， 物 品 E 需 要 占 用 C o s t = 8 ， 而 背 包 容 量 j = 9 > C o s t , 所 以 背 包 可 以 放 入 E 這 件 物 品 如 果 放 入 E ， 那 麼 就 要 騰 出 E 的 空 間 ， 所 以 F 1 [ 5 ] [ 9 ] = F [ 5 − 1 ] [ 9 − C o s t E ] + W e a l t h E = 10 如 果 不 放 入 E ， 那 麼 不 需 要 騰 出 E 的 空 間 ， 所 以 F E [ 5 ] [ 9 ] = F [ 4 ] [ 9 ] = 13 ， 可 以 看 到 不 放 入 E 反 而 讓 背 包 的 總 價 值 更 大 當[i，j] = [5，9]時，物品E需要占用Cost=8，而背包容量j=9 > Cost,是以背包可以放入E這件物品\\ 如果放入E，那麼就要騰出E的空間，是以F_1[5][9] = F[5-1][9-Cost_E] + Wealth_E = 10\\ 如果不放入E，那麼不需要騰出E的空間，是以F_E[5][9] = F[4][9]=13，可以看到不放入E反而讓背包的總價值更大\\ 當[i，j]=[5，9]時，物品E需要占用Cost=8，而背包容量j=9>Cost,是以背包可以放入E這件物品如果放入E，那麼就要騰出E的空間，是以F1[5][9]=F[5−1][9−CostE]+WealthE=10如果不放入E，那麼不需要騰出E的空間，是以FE[5][9]=F[4][9]=13，可以看到不放入E反而讓背包的總價值更大
是以并不是說物品E可以放入就馬上放入，因為每放入一件物品都要騰出相應的空間
V 騰 出 的 空 間 = C o s t i V_{騰出的空間} = Cost_i V騰出的空間=Costi
而騰出的空間可以放入其它物品，而有可能放入其它的物品價值總和大于物品E的價值。
⑤ 代碼實作
public class Solution{
public int dp(int[] wealth, int[] cost, int V, int N){
//特殊狀态處理
if(wealth.length != cost.length){return -1;}
if(wealth.length == 0){return 0;}
if(wealth.length == 1){
if(cost[0] > V){
return 0;
}else{
return wealth[0];
}
}
int[][] F = new int[N + 1][V+1];
//邊界值處理
for(int i = 1; i < N + 1; i++){
for(int j = 1; j < V + 1; j++){
//先假設不能放入容量為j的背包
F[i][j] = F[i-1][j];
//判斷能不能放入背包
if(j >= cost[i-1]){
F[i][j] = Math.max(F[i-1][j], F[i-1][j-cost[i-1]] + wealth[i-1]);
}
}
}
return F[N][V];
}
}
時間有限，能力有限，若有誤希望能夠指出，樂意與大家交流！