javascript中的动态规划是什么_如何解决经典背包问题-js教程-PHP中文网

javascript中的动态规划是什么_如何解决经典背包问题

狼影

发布： 2025-12-13 23:40:03

原创

780人浏览过

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

javascript中的动态规划是什么_如何解决经典背包问题

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

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

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

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

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

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

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

立即学习“Java免费学习笔记（深入）”；

Figma

Figma 是一款基于云端的 UI 设计工具，可以在线进行产品原型、设计、评审、交付等工作。

1371

查看详情

状态转移逻辑很直接：

如果不选第 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>

登录后复制

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

以上就是javascript中的动态规划是什么_如何解决经典背包问题的详细内容，更多请关注php中文网其它相关文章！