JavaScript背包问题动态规划详解

function knapsack(weights, values, capacity) {
  const n = weights.length;
  // 创建二维DP数组
  const dp = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0));
// 填充DP表
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = Math.max(
dp[i - 1][w],  // 不放当前物品
dp[i - 1][w - weights[i - 1]] + values[i - 1]  // 放当前物品
);
} else {
dp[i][w] = dp[i - 1][w];  // 超重，不能放
}
}
}
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)); // 输出：10

function knapsackOptimized(weights, values, capacity) {
  const dp = Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let w = capacity; w >= weights[i]; w--) {
dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[capacity];
}