0/1 背包 II

要求要求恰装满背包
在初始化时除了 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

   例子 2：c[] = { 6,3,5,4,6}, w[]={2,2,6,5,4}, v=10

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; **