有 N 件物品和一個(gè)容量為 V 的背包汰蓉。第 i 件物品的費(fèi)用是 c[i]丽旅，價(jià)值是 w[i]贡未。求解將哪些物品裝入背包可使價(jià)值總和最大
f[i][v]表示前 i 件物品恰放入一個(gè)容量為 v 的背包可以獲得的最大價(jià)值裹匙，狀態(tài)
方程：
f[i][v] = max{f[i ? 1][v], f[i ? 1][v ? c[i]] + w[i]}
f[i][v] 依賴(lài)于 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];
}
可以對(duì)空間做優(yōu)化儿惫，用一位數(shù)組，由于 f[i][v]依賴(lài) f[i-1][v-c[i]]列荔，需要保留上一行 v 之前的記錄敬尺，所以要從右往左計(jì)算。
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];
}
