01背包问题是在限定容量下使物品价值最大化，每物仅可选一次；使用动态规划，通过状态转移方程dpi = max(dpi-1, dpi-1] + value[i])求解；JavaScript中可用二维数组实现，再优化为一维数组从后往前更新，降低空间复杂度。
背包问题是动态规划中的经典问题，主要分为01背包、完全背包和多重背包等类型。这里重点介绍最基础的01背包问题及其在JavaScript中的实现方式。
什么是01背包问题？
给定一个固定容量的背包和一组物品，每个物品有重量和价值，每种物品只能选择一次（拿或不拿），目标是在不超过背包容量的前提下，使装入背包的物品总价值最大。
动态规划解法思路
使用二维数组 dp[i][w] 表示前 i 个物品在容量为 w 时能获得的最大价值：
- 对于每个物品，有两种选择：放入背包或不放入
- 如果不放入，dp[i][w] = dp[i-1][w]
- 如果放入（前提是物品重量 ≤ w），dp[i][w] = dp[i-1][w-weight[i]] + value[i]
- 取两者最大值即可
JavaScript代码实现
以下是解决01背包问题的完整JavaScript函数：
立即学习“Java免费学习笔记（深入）”；
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
空间优化：一维数组解法
可以将空间复杂度从 O(n×W) 降到 O(W)，使用一维数组从后往前更新：
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];
}
基本上就这些。掌握状态定义和转移方程是关键，理解后可扩展到完全背包等问题。
