用 JavaScript 实现 0-1 背包问题
参考答案
// 每个物品重量 w[i]、价值 v[i],容量 cap
function knapsack(w, v, cap) {
const dp = new Array(cap + 1).fill(0);
for (let i = 0; i < w.length; i++) {
for (let c = cap; c >= w[i]; c--) { // 倒序保证 0-1(每件只用一次)
dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);
}
}
return dp[cap];
}
要点:
- 一维滚动数组,容量维度必须倒序,否则变成完全背包;
- 时间 O(n*cap),空间 O(cap);
- 要输出选取方案需二维 dp + 回溯;重量可能为 0 或负数需特判。