有 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
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 2 | 0 | 0 | 0 | 4 | 5 | 5 | 5 | 9 | 9 | 9 | 9 |
| 3 | 0 | 0 | 0 | 4 | 5 | 6 | 6 | 9 | 10 | 11 | 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 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
| 2 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 9 | 9 | 9 | 9 |
| 3 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 9 | 11 | 11 | 14 |
| 4 | 0 | 0 | 6 | 6 | 9 | 9 | 9 | 10 | 11 | 13 | 14 |
| 5 | 0 | 0 | 6 | 6 | 9 | 9 | 12 | 12 | 15 | 15 | 15 |
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];
}
