动态规划解决经典背包问题全解析

哈喽！今天心血来潮给大家带来了《动态规划解经典背包问题详解》，想必大家应该对文章都不陌生吧，那么阅读本文就都不会很困难，以下内容主要涉及到，若是你正在学习文章，千万别错过这篇文章~希望能帮助到你！

动态规划是解决重叠子问题的算法策略，背包问题因其阶段性决策、子问题重叠和最优子结构而适合DP；JavaScript中可用二维或空间优化的一维数组实现。

动态规划（Dynamic Programming，简称 DP）在 JavaScript 中不是某种内置语法，而是一种解题思想和算法策略：把大问题拆成重叠的子问题，用数组（或对象）“记下来”已算过的中间结果，避免重复计算，从而提升效率。

背包问题为什么适合用动态规划？

0-1 背包问题的经典描述是：给定 n 个物品，每个有重量 w[i] 和价值 v[i]，背包容量为 W，每件物品最多选一次，求能装入的最大总价值。它的关键特征是：

• 决策具有阶段性（对每个物品，选或不选）
• 子问题重叠（比如“前 3 个物品、容量 5”这个状态会被多次用到）
• 最优解依赖于更小规模的最优解（无后效性）

这些正是动态规划适用的信号。

JavaScript 中实现 0-1 背包的二维 DP 解法

定义 dp[i][j] 表示考虑前 i 个物品、背包容量为 j 时能获得的最大价值。

状态转移逻辑很直接：

• 如果不选第 i−1 个物品（索引从 0 开始）：dp[i][j] = dp[i−1][j]
• 如果选它（前提是 j ≥ w[i−1]）：dp[i][j] = dp[i−1][j − w[i−1]] + v[i−1]
• 取两者较大值

代码示例（简洁可运行）：

function knapsack(weights, values, W) {
  const n = weights.length;
  // 初始化二维数组，dp[i][j] 表示前 i 个物品、容量 j 的最大价值
  const dp = Array(n + 1).fill().map(() => Array(W + 1).fill(0));
<p>for (let i = 1; i <= n; i++) {
for (let j = 0; j <= W; j++) {
dp[i][j] = dp[i - 1][j]; // 默认不选
if (j >= weights[i - 1]) {
dp[i][j] = Math.max(
dp[i][j],
dp[i - 1][j - weights[i - 1]] + values[i - 1]
);
}
}
}</p><p>return dp[n][W];
}</p><p>// 示例调用
console.log(knapsack([2, 1, 3], [2, 8, 4], 4)); // 输出：10（选第 2 和第 3 个物品）</p>

空间优化：一维数组就够了

观察发现，每次只依赖上一行，所以可用一维数组 dp[j] 滚动更新。但注意：内层循环要从右往左遍历容量，否则会重复使用刚更新的值（导致变成完全背包）。

function knapsackOptimized(weights, values, W) {
  const dp = Array(W + 1).fill(0);
<p>for (let i = 0; i < weights.length; i++) {
// 从大到小遍历，防止覆盖未使用的旧状态
for (let j = W; j >= weights[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}</p><p>return dp[W];
}</p>

基本上就这些。动态规划的核心不在语法，而在建模——想清楚“状态是什么”“怎么转移”“边界在哪”。背包问题练熟了，再碰最长公共子序列、爬楼梯、编辑距离，思路就顺多了。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~