0/1 背包

有 N 件物品和一个容量为 V 的背包。第 i 件物品的费用是 c[i]，价值是 w[i]。求解将哪些物品装入背包可使价值总和最大

f[i][v]表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值，状态
方程：

f[i][v] = max{f[i − 1][v], f[i − 1][v − c[i]] + w[i]}

f[i][v] 依赖于 f[i-1][v]和 f[i-1][v-c[i]]

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

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

public static int zeroOneKnapsack(int c[], int w[], int vol) {
    int len = c.length;
    if (len == 0 || len != w.length) {
        return 0;
    }

    int f[][] = new int[len + 1][vol + 1];
    for (int i = 1; i <= len; i++) {
        for (int v = 1; v <= vol; v++) {
            if (i == 0) {
                f[i][v] = 0;
                continue;
            }
            f[i][v] = f[i - 1][v];
            if (v >= w[i - 1]) {
                f[i][v] = Math.max(f[i][v], f[i - 1][v - w[i - 1]] + c[i - 1]);
            }
        }
    }
    return f[len][vol];
}

可以对空间做优化，用一位数组，由于 f[i][v]依赖 f[i-1][v-c[i]]，需要保留上一行 v 之前的记录，所以要从右往左计算。

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 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];
}