用js写一个货郎背包问题

货郎背包问题是一个经典的组合优化问题，它的目标是在限制了背包容量和物品数量的情况下，选择一些物品放入背包，使得背包中物品的总价值最大化。

下面是使用JavaScript实现货郎背包问题的代码：

function knapsack(capacity, weights, values, n) {
  var i, w, j, val = [];
  for (i = 0; i <= n; i++) {
    val[i] = [];
  }

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

  return val[n][capacity];
}

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

console.log(knapsack(capacity, weights, values, n)); // 输出220

在这个实现中，我们使用了动态规划的思想，创建了一个二维数组来存储每个背包容量和物品数量下的最优解。具体地，我们使用 val[i][w] 表示将前 i 个物品放入容量为 w 的背包中的最大价值。对于每个物品 i，我们有两种选择：将其放入背包中或不放入。如果将其放入背包中，则背包中的剩余容量为 w - weights[i-1]，此时背包中的总价值为 values[i-1] + val[i-1][w - weights[i-1]]；如果不放入，则背包中的总价值为 val[i-1][w]。我们选择其中较大的一个作为 val[i][w] 的值。最终的答案为 val[n][capacity]。