前言
背包问题只是动态规划问题下的一个分类，求解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];
}
}
时间有限，能力有限，若有误希望能够指出，乐意与大家交流！