← 返回完整题库
JavaScript困难

用 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 或负数需特判。

本题来自 计算机知识面试题库,共 921 道题。