JS实现背包
背包问题的基本概念
背包问题是一个经典的动态规划问题，通常分为 0-1背包 和 完全背包 两种类型。0-1背包中，每个物品只能选择一次；完全背包中，每个物品可以选择多次。以下是使用 JavaScript 实现 0-1背包的示例代码。
0-1背包问题的动态规划解法
动态规划的核心是构建一个二维数组 dp，其中 dp[i][j] 表示从前 i 个物品中选择，总重量不超过 j 时的最大价值。
function knapsack(weights, values, capacity) {
const n = weights.length;
const dp = Array(n + 1).fill().map(() => 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];
}
}
}
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)); // 输出最大价值优化空间复杂度
二维数组 dp 可以优化为一维数组，减少空间占用：
function knapsackOptimized(weights, values, capacity) {
const dp = Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let j = capacity; j >= weights[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
console.log(knapsackOptimized(weights, values, capacity)); // 输出相同结果完全背包问题的解法
完全背包允许物品重复选择，只需调整内层循环的方向：
function completeKnapsack(weights, values, capacity) {
const dp = Array(capacity + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
for (let j = weights[i]; j <= capacity; j++) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
console.log(completeKnapsack(weights, values, capacity)); // 输出完全背包的最大价值应用场景
背包问题广泛应用于资源分配、投资组合优化等场景。动态规划解法的时间复杂度为 $O(n \cdot W)$，其中 $n$ 是物品数量，$W$ 是背包容量。
