编辑代码

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);