编辑代码

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = new Array(n + 1).fill(0).map(() => new 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];
      }
    }
  }

  const selectedItems = [];
  let i = n;
  let j = capacity;
  while (i > 0 && j > 0) {
    if (dp[i][j] !== dp[i - 1][j]) {
      selectedItems.push(i - 1);
      j -= weights[i - 1];
    }
    i--;
  }

  return {
    maxValue: dp[n][capacity],
    selectedItems: selectedItems.reverse(),
  };
}

// 示例用法
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 8;

const result = knapsack(weights, values, capacity);
console.log("最大总价值:", result.maxValue);
console.log("选中的物品:", result.selectedItems);