用js实现背包算法

背包算法是一个经典的动态规划问题，可以用 JavaScript 实现。下面是一个基本的实现：

function knapsack(capacity, weights, values, n) {
  let i, w;
  let K = new Array(n + 1);

  for (i = 0; i <= n; i++) {
    K[i] = new Array(capacity + 1);
  }

  for (i = 0; i <= n; i++) {
    for (w = 0; w <= capacity; w++) {
      if (i === 0 || w === 0) {
        K[i][w] = 0;
      } else if (weights[i - 1] <= w) {
        K[i][w] = Math.max(
          values[i - 1] + K[i - 1][w - weights[i - 1]],
          K[i - 1][w]
        );
      } else {
        K[i][w] = K[i - 1][w];
      }
    }
  }

  return K[n][capacity];
}

这个函数接受四个参数：背包容量 `capacity`，物品重量数组 `weights`，物品价值数组 `values`，以及物品数量 `n`。它返回能够装入背包的最大价值。

相关问题

用js 写一个 背包算法

背包算法是一种经典的解决背包问题的算法。背包问题是指：给定一个有限容量的背包和若干物品，每个物品都有一个重量和一个价值，在保证不超过背包容量的前提下，选择物品，使得物品总价值最大。

以下是一个使用 JavaScript 实现的背包算法的示例：

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

let capacity = 50;
let values = [60, 100, 120];
let weights = [10, 20, 30];
let n = values.length;

console.log(knapsack(capacity, weights, values, n));

上面的代码实现了 0/1 背包问题的动态规划算法，其中 `dp[i][j]` 表示前 `i` 件物品放入容量为 `j` 的背包可以获得的最大价值。

请把前面的背包算法示例代码用JS重写一遍

const knapsack = (items, capacity) => {
  const matrix = Array(items.length + 1)
    .fill(null)
    .map(() => Array(capacity + 1).fill(0));

  for (let i = 1; i <= items.length; i++) {
    const { weight, value } = items[i - 1];
    for (let j = 0; j <= capacity; j++) {
      if (weight > j) {
        matrix[i][j] = matrix[i - 1][j];
      } else {
        matrix[i][j] = Math.max(
          matrix[i - 1][j],
          matrix[i - 1][j - weight] + value
        );
      }
    }
  }

  return matrix[items.length][capacity];
};

const items = [
    { weight: 2, value: 6 },
    { weight: 2, value: 10 },
    { weight: 3, value: 12 }
];

console.log(knapsack(items, 5))

上面是背包算法的 JavaScript 示例代码。其中，函数 knapsack() 接受两个参数：items 和 capacity。items 是物品数组，其中每个物品都有 weight 和 value 属性；capacity 是背包的容量。函数返回背包中最大价值。