有 N 种物品和一个容量为 V 的背包，每种物品都有无限件可用。第 i 种物品的费用是 c[i]，价值是 w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。状态方程：
f[i][v] = max{f[i − 1][v], f[i][v − c[i]] + w[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 | 8 | 8 | 8 | 12 | 12 |
| 2 | 0 | 0 | 0 | 4 | 5 | 5 | 8 | 9 | 10 | 12 | 13 |
| 3 | 0 | 0 | 0 | 4 | 5 | 6 | 8 | 9 | 10 | 12 | 13 |
例子 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 | 12 | 12 | 18 | 18 | 24 | 24 | 30 |
| 2 | 0 | 0 | 6 | 6 | 12 | 12 | 18 | 18 | 24 | 24 | 30 |
| 3 | 0 | 0 | 6 | 6 | 12 | 12 | 18 | 18 | 24 | 24 | 30 |
| 4 | 0 | 0 | 6 | 6 | 12 | 12 | 18 | 18 | 24 | 24 | 30 |
| 5 | 0 | 0 | 6 | 6 | 12 | 12 | 18 | 18 | 24 | 24 | 30 |
public static int completeKnapsack(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 = w[i - 1]; v <= vol; v++) {
f[v] = Math.max(f[v], f[v - w[i - 1]] + c[i - 1]);
}
}
return f[vol];
}
