JS实现背包
背包问题的基本概念
背包问题是一个经典的动态规划问题，通常分为0-1背包和完全背包两种类型。0-1背包问题中，每种物品只能选择一次；完全背包问题中，每种物品可以选择多次。
0-1背包问题的实现
以下是0-1背包问题的JavaScript实现代码。假设给定物品的重量数组weights、价值数组values和背包容量capacity。
function knapsack01(weights, values, capacity) {
const n = weights.length;
const dp = Array.from({ length: n + 1 }, () => 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(knapsack01(weights, values, capacity)); // 输出最大价值完全背包问题的实现
完全背包问题允许每种物品选择多次。以下是其JavaScript实现代码。
function completeKnapsack(weights, values, capacity) {
const n = weights.length;
const dp = Array(capacity + 1).fill(0);
for (let i = 0; i < n; i++) {
for (let j = weights[i]; j <= capacity; j++) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 8;
console.log(completeKnapsack(weights, values, capacity)); // 输出最大价值优化空间复杂度
上述0-1背包问题的实现使用了二维数组，可以优化为一维数组以节省空间。
function knapsack01Optimized(weights, values, capacity) {
const n = weights.length;
const dp = Array(capacity + 1).fill(0);
for (let i = 0; i < n; i++) {
for (let j = capacity; j >= weights[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 8;
console.log(knapsack01Optimized(weights, values, capacity)); // 输出最大价值注意事项
- 动态规划表格的初始化需要根据问题需求调整。
- 完全背包问题的内层循环是正向遍历，而0-1背包问题的优化版本是逆向遍历。
- 确保输入的
weights和values数组长度一致，且容量为非负数。
