要求要求恰装满背包
在初始化时除了 f[0]为 0 其它 f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
可以这样理解：初始化的 f 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 0 的背包可能被价值为 0 的 nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 0，所以初始时状态的值也就全部为 0 了。
例子 1：c[] = {4,5,6}, w[]={3,4,5} v=9
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ |
| 1 | 0 | -∞ | -∞ | 4 | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ |
| 2 | 0 | -∞ | -∞ | 4 | 5 | -∞ | -∞ | 9 | -∞ | -∞ |
| 3 | 0 | -∞ | -∞ | 4 | 5 | 6 | -∞ | 9 | 10 | 11 |
例子 2：c[] = { 6,3,5,4,6}, w[]={2,2,6,5,4}, v=10
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ |
| 1 | 0 | -∞ | 6 | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ |
| 2 | 0 | -∞ | 6 | -∞ | 9 | -∞ | -∞ | -∞ | -∞ | -∞ | -∞ |
| 3 | 0 | -∞ | 6 | -∞ | 9 | -∞ | 5 | -∞ | 11 | -∞ | 14 |
| 4 | 0 | -∞ | 6 | -∞ | 9 | 4 | 5 | 10 | 11 | 13 | 14 |
| 5 | 0 | -∞ | 6 | -∞ | 9 | 4 | 5 | 10 | 11 | 13 | 14 |
public static int zeroOneKnapsackII(int c[], int w[], int vol) {
int len = c.length;
if (len == 0 || len != w.length) {
return 0;
}
int f[] = new int[vol + 1];
for (int v = 1; v <= vol; v++)
f[v] = Integer.MIN_VALUE;
for (int i = 1; i <= len; i++) {
for (int v = vol; v >= w[i - 1]; v--) {
f[v] = Math.max(f[v], f[v - w[i - 1]] + c[i - 1]);
}
}
return f[vol];
}
区别在
** f[v] = Integer.MIN_VALUE; **
