双约束背包问题JavaScript代码修复：测试用例2未通过

这是典型的二维约束0-1背包问题，需要同时考虑重量和体积两个限制，选择物品组合以获得最高总价值。原代码仅通过测试1，大概率是只处理了单一约束（比如仅考虑重量），或是DP状态转移逻辑未覆盖二维条件。

修复后的完整代码 #

function knapsack(maxWeight, maxSize, items) {
  // 初始化二维DP数组：dp[weight][size] 对应当前约束下的最大价值
  const dp = Array.from({ length: maxWeight + 1 }, () => 
    Array(maxSize + 1).fill(0)
  );

  for (const { weight, size, value } of items) {
    // 0-1背包必须逆序遍历，避免重复选取同一物品
    for (let w = maxWeight; w >= weight; w--) {
      for (let s = maxSize; s >= size; s--) {
        // 状态转移：比较选当前物品与不选的价值，取最大值
        dp[w][s] = Math.max(dp[w][s], dp[w - weight][s - size] + value);
      }
    }
  }

  return dp[maxWeight][maxSize];
}

// 给定物品列表（匹配测试用例预期）
const items = [
  { weight: 20, size: 20, value: 15 },
  { weight: 30, size: 30, value: 20 },
  { weight: 30, size: 80, value: 50 },
  { weight: 15, size: 10, value: 10 }
];

// 验证测试用例
console.log(knapsack(50, 50, items)); // 输出35（符合测试1预期）
console.log(knapsack(30, 100, items)); // 输出50（符合测试2预期）

关键修复点说明 #

1. 二维DP数组设计：
   用dp[w][s]存储「重量不超过w、体积不超过s」时的最大价值，完整覆盖了两个约束条件，解决了原代码可能只处理单一维度的问题。

2. 逆序遍历逻辑：
   0-1背包中每个物品只能选一次，逆序遍历重量和体积维度，避免同一物品被重复计入价值（正序遍历会变成完全背包，允许重复选物品）。

3. 正确的状态转移：
   对每个物品，同时检查重量和体积是否满足限制，通过Math.max(dp[w][s], dp[w-weight][s-size] + value)判断选或不选当前物品的最优解。

内容的提问来源于stack exchange，提问作者Gihan Punarji