动态规划之零一背包问题
一、题目
有 NN 件物品和一个容量为 VV 的背包，每件物品有各自的价值，要求在有限的背包容量下，装入的物品总价值最大。
「0-1 背包」是较为简单的动态规划问题，也是其余背包问题的基础。
动态规划是不断决策求最优解的过程，「0-1 背包」即是不断对第 ii 个物品的做出决策，「0-1」正好代表不选与选两种决定。
二、题目分析
关于动态算法，了解的人可能需要2~3分钟，不懂的人可能需要2 ~ 3天，了解动态算法的思想很重要。
2.1 二维数据解法
（1）状态f[i][j]定义：前 i 个物品，背包容量 j 下的最优解（最大价值）：
当前的状态依赖于之前的状态，可以理解为从初始状态f[0][0] = 0开始决策，有 N 件物品，则需要 N 次决 策，每一次对第 i 件物品的决策，状态f[i][j]不断由之前的状态更新而来。
（2）当前背包容量不够（j < v[i]），没得选，因此前 i 个物品最优解即为前 i−1 个物品最优解：
对应代码：f[i][j] = f[i - 1][j]。
（3）当前背包容量够，可以选，因此需要决策选与不选第 i 个物品：
选：f[i][j] = f[i - 1][j - v[i]] + w[i]。
不选：f[i][j] = f[i - 1][j] 。
我们的决策是如何取到最大价值，因此以上两种情况取 max() 。
代码实现
public class MyBackpackSolution {
public static void main(String[] args) {
int[] weight = {2,2,6,5,4};
int[] value = {6,3,5,4,6};
int w = 10;
int n = weight.length;
int[][] maxVal = new int[n + 1][w + 1];
// 由于循环从1开始，所以在遍历weight、value数组获取数据时坐标需要减一
for(int i=1; i<=n; i++) {
for (int j=1; j<=w; j++) {
if (j < weight[i-1]) {
maxVal[i][j] = maxVal[i-1][j];
} else {
maxVal[i][j] = Math.max(maxVal[i-1][j], maxVal[i-1][j - weight[i-1]] + value[i-1]);
}
}
}
System.out.println(maxVal[n][w]);
}
}2.2 一维数组解法
将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变形。
为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的i与j最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。
（1）状态f[j]定义：NN 件物品，背包容量j下的最优解。
（2）注意枚举背包容量j必须从m开始。
（3）为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。
（4）例如，一维状态第i轮对体积为 33 的物品进行决策，则f[7]由f[4]更新而来，这里的f[4]正确应该是f[i - 1][4]，但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i][4]。当逆序枚举背包容量j时，我们求f[7]同样由f[4]更新，但由于是逆序，这里的f[4]还没有在第i轮计算，所以此时实际计算的f[4]仍然是f[i - 1][4]。
（5）简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。
状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i] 。
public class MyBackpackSolution1 {
public static void main(String[] args) {
int[] weight = {2,2,6,5,4};
int[] value = {6,3,5,4,6};
int w = 10;
int n = weight.length;
int[] maxVal = new int[w + 1];
for (int i = 1; i<= n; i++) {
for (int j=w; j>= 1; j--) {
if (j < weight[i-1]) {
maxVal[j] = maxVal[j];
} else {
maxVal[j] = Math.max(maxVal[j], maxVal[j - weight[i - 1]] + value[i-1]);
}
}
}
System.out.println(maxVal[w]);
}
}三、总结
动态规划的核心还是找子问题的最有解，确定状态转移公式：
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i])