0-1背包问题
问题
n个物体，它们各自有重量和价值，给定一个有容量的背包，如何让背包里装入的物体价值总和最大？
例如：
物品数量：num=4， 背包容量： capacity=8
| i | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| w(体积) | 2 | 3 | 4 | 5 |
| v(价值) | 3 | 4 | 5 | 6 |
原理
对于任意第 i 个 物品，只可能存在两种可能: ①装进背包 or ②不装进背包。
在此之前先定义一些符号表示:
val(i, j) : 表示当前背包可用空间为j，前i个物品最佳组合对应的价值。
因此，可以得到这么一个递推关系式:
当前物品装不下，j < w(i) val(i, j) = val (i - 1, j)
能装下当前物品，j >= w(i) val(i, j) = max { val(i - 1, j - w(i)) + v(i), val(i - 1, j) }
构建表格
在理解了这个递归关系式后，我们根据这个关系式来填写如下的表格，首先呢初始化边界条件，即 val(0, j) = val (i, 0) = 0
这里举几个典型的栗子吧
比如说 val(2, 2), 此时背包容量j = 2，而i为2的背包重量w(2)为3，此时装不下，所以val(2, 2) = val (1, 2) = 3;
再举个典型的例子，对于val(3, 4)，对于i= 3的背包，w(3) = 4，而此时背包容量为4，能够装得下，val(3, 4) =max { val(2, 4 - w(3)) + v(3), val(2, 4) } =max{ val(2, 0) + v(3), 4} = max{ 5, 4 } = 5;
就这样，按着之前我们推到的递推关系式来填写表格即可。
这是整个建立这张表的过程实现:
/**
* w[i] 第i个物品的重量
* v[i] 第i个物品的价值
*/
public void findMax() { //利用动态规划
for (int i = 1; i < num; i++) { // 开始填写第 i 行，逐行填写
for (int j = 1; j < capacity; j++) { // j 背包可装载的容量
if (j < w[i]) { // 如果物品放不进背包
val[i][j] = val[i - 1][j];
} else { // 能放进背包
v[i][j] = Math.max(val[i - 1][j - w[i]] + v[i], val[i - 1][j]);
}
}
}
}
回溯找出背包方案
在构建了表格后，我们已经模拟了整个程序执行的过程，这个过程记录了所有的步骤和相关信息。而我们从表格中能够得出的信息是，val(i ,j)的最大值其实就在val(4, 8)位置，也就是表格的最右下方。我们还得知道这个最大值的选择方案是什么，即我们的背包需要带上哪几个物品？
这就是我们进行回溯的意义了。
我们回溯的过程很简单，相当于从最后一个物品开始往回倒推，查看每一个物品是否被选择？
从最右下角的元素开始，对于每一个val(i, j) ，需要满足以下规则:
① val(i , j) = val(i - 1, j) ，说明没有选择第i个物品，转到val(i - 1, j)；
② val(i , j) ≠ val(i - 1, j)，则说明选择了第i个物品，转到val(i - 1, j - w[i]);
③ 重复以上步骤直到 i = 0 为止。
下面是回溯的实现:
/**
* i , j 分别为第i个物品 和 背包剩余空间j
* res[i] 表示第i个物品是否被装 ，取值→ 0 / 1
*/
public void traceBack(int i, int j) { // 回溯
if (i > 0) {
if (v[i][j] == v[i- 1][j]) { // 没有装此物品
res[i] = 0;
traceBack(i - 1, j);
} else {
res[i] = 1;
traceBack(i - 1, j - w[i]);
}
}
}
（未完待续）后面还将进行一些其他背包问题的分析，尽量全面一点吧...
