0-1 背包问题的动态规划实现（Java）
01背包是最经典的动态规划问题。假设有一堆化石，因为是化石所以价值和重量无关。你有一个背包，承重有限。从化石中挑选总重量不超过背包能力、总价值又最大的问题就是01背包问题。常见算法有贪心算法和动态规划算法（DP算法）。本文基于我github上的一个老项目：https://github.com/davelet/dp-just-code-no-word。
01的叫法是因为不能把化石打碎，要么整个拿要么不拿
问题初始化
假设背包称重最大9个单位。你面前有4个化石，重量分别是2、3、4、5，价值分别是3，4，5，6。问题的描述位于文件DpSourceData.java中：
static final int[] volume = {0, 2, 3, 4, 5};// 4个物品的占用
static final int[] values = {0, 3, 4, 5, 6};// 4个物品的价值
static final int maxVolume = 9; // 最大体积 可以用其他值尝试 比如8
数组使用0前缀是因为一方面物品序号就是数组序号，另一方面dp的二维数组也是有围栏的。
二维数组实现
动态规划最常用的解放是通过二维数组记录，也就是一个表格。这个表的宽度是背包容量+1，高度是物品数量+1。
因为动态规划的过程是基于子问题的，所以一行一行的走（走到当前行就看一眼上一行）。 表格有围栏，所以用0围起来：
int length = DpSourceData.volume.length;
int width = DpSourceData.maxVolume + 1;
Integer[][] table = new Integer[length][width];
for (int i = 0; i < length; i++) {
for (int j = 0; j < width; j++) {
if (i == 0) { // 第一行全是0
table[i][j] = 0;
} else if (j == 0) { // 第一列也是0
table[i][j] = 0;
} else { // 从第二行第二列开始
...
}
}
}
围栏的目的是当一个东西都不选也是一个子问题。
从第二行第二列开始动态规划。如果当前容量可以容纳物品i（即下面代码中的j >= DpSourceData.volume[i]），就判断加入当前物品后的价值是否提升了。 如果提升了就加入，否则价值不变。 加入的方法是看一下留置足够空间的背包的最大价值，再加上当前物品的价值（即table[i - 1][j - DpSourceData.volume[i]] + DpSourceData.values[i]）。
Integer pre = table[i - 1][j];
int nxt = pre; // 放不下就去之前的
if (j >= DpSourceData.volume[i]) {
nxt = table[i - 1][j - DpSourceData.volume[i]] + DpSourceData.values[i];
}
table[i][j] = max(pre, nxt);
这样整个算法就结束了，最优解就是表格右下角的值。
从算法过程也能看出使用数组的好处：不会更新数据，还能随机读取。
最优解的构成
这个最优解是哪些化石组成的呢？
程序打印出了表格：
0 0 0 0 0 0 0 0 0 0
0 0 3 3 3 3 3 3 3 3
0 0 3 4 4 7 7 7 7 7
0 0 3 4 5 7 8 9 9 12
0 0 3 4 5 7 8 9 10 12
可以看到第二行（第一个物品）中从第三列开始取了当前物品，也就是背包容量足够时可以拿当前物品。
所以既然只有一个物品，并且被选取了，那么后面都写3不就行了。这样可以，但是从算法复杂性角度没好处所以没用。实际应用中使用是应该的。
当有两个物品时（也就是第三行），因为第二个物品的价值更大。给第二个物品留置空间就要把第一个扔掉，所以查询的值是上一行的第一列（也就是围栏，可以发现围栏的作用了）。到了第六列的时候（也就是背包容量达到7了），发现两个都可以放下了（这时候又可以优化了：总共就两个还都被拿走了，那当前行后面的都可以是7了）。
后面的过程都一样，一直到最后一行，你可以发现倒数第二行就已经达到最大值12了，说明最后一个物品没有被选取，而倒数第二个物品（也就是第三个）。 也就是说增加物品价值没变化就是没被选取。剔除了被选取物品后，继续判断更新背包的子问题，也就是下面代码中的right -= DpSourceData.volume[i]：
int right = width - 1;
for (int i = length - 1; i > 0; i--) { // 逐行回退
if (!table[i][right].equals(table[i - 1][right])) { // 相等就继续回退，否则输出当前元素
System.out.println(DpSourceData.values[i]);
right -= DpSourceData.volume[i]; // 回退空间到之前
}
}
这样就逆序输出了被选取的物品价值。简单修改输出就能输出物品下标。
一维数组实现
如果只需要求得最大价值而不用记录物品组成，可以使用一维数组：
int[] table = new int[width];
for (int i = 0; i < length; i++) {// 一次一次的刷
for (int j = width-1; j >= 0; j--) {
if (j >= DpSourceData.volume[i]){ // 每一次看能替换就替换
table[j] = max(table[j], table[j - DpSourceData.volume[i]] + DpSourceData.values[i]);
}
}
}
了解的二维动态规划的过程，一维的也很简单，就不解释了。
总结
01背包问题的解法挺多的。除了穷举法，其他性能都差不多。当然贪心算法难以找到最优解（性能最好），因为它优先选取价值最大的。以上面为例，价值最大的恰好没选取。
- 分享到
-
-
