当前位置：首页 > JavaScript

JS实现背包

2026-03-15 03:44:41JavaScript

背包问题的基本概念

背包问题是一个经典的动态规划问题，通常分为 0-1背包 和 完全背包 两种类型。0-1背包中，每个物品只能选择一次；完全背包中，每个物品可以选择多次。以下是使用 JavaScript 实现 0-1背包的示例代码。

0-1背包问题的动态规划解法

动态规划的核心是构建一个二维数组 dp，其中 dp[i][j] 表示从前 i 个物品中选择，总重量不超过 j 时的最大价值。

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array(n + 1).fill().map(() => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= capacity; j++) {
      if (weights[i - 1] <= j) {
        dp[i][j] = Math.max(
          dp[i - 1][j],
          dp[i - 1][j - weights[i - 1]] + values[i - 1]
        );
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  return dp[n][capacity];
}

const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 8;
console.log(knapsack(weights, values, capacity)); // 输出最大价值

优化空间复杂度

二维数组 dp 可以优化为一维数组，减少空间占用：

function knapsackOptimized(weights, values, capacity) {
  const dp = Array(capacity + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    for (let j = capacity; j >= weights[i]; j--) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }

  return dp[capacity];
}

console.log(knapsackOptimized(weights, values, capacity)); // 输出相同结果

完全背包问题的解法

完全背包允许物品重复选择，只需调整内层循环的方向：

JS实现背包

function completeKnapsack(weights, values, capacity) {
  const dp = Array(capacity + 1).fill(0);

  for (let i = 0; i < weights.length; i++) {
    for (let j = weights[i]; j <= capacity; j++) {
      dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }

  return dp[capacity];
}

console.log(completeKnapsack(weights, values, capacity)); // 输出完全背包的最大价值