J*aScript动态规划_背包问题解决方案

技术教程
2025-11-23 17:05:02

01背包问题是在限定容量下使物品价值最大化，每物仅可选一次；使用动态规划，通过状态转移方程dpi = max(dpi-1, dpi-1] + value[i])求解；J*aScript中可用二维数组实现，再优化为一维数组从后往前更新，降低空间复杂度。

javascript动态规划_背包问题解决方案

背包问题是动态规划中的经典问题，主要分为01背包、完全背包和多重背包等类型。这里重点介绍最基础的01背包问题及其在J*aScript中的实现方式。

什么是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]
取两者最大值即可

J*aScript代码实现

以下是解决01背包问题的完整J*aScript函数：

达奇AI论文写作

达奇AI论文辅助写作平台，在校学生、职场精英都在用的AI论文辅助写作平台

106 查看详情达奇AI论文写作

function knapsack(weights, values, capacity) {
  const n = weights.length;
  // 创建二维DP数组
  const dp = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0));
<p>// 填充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];  // 超重，不能放
}
}
}</p><p>return dp[n][capacity];
}</p><p>// 示例使用
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 8;
console.log(knapsack(weights, values, capacity)); // 输出：10</p>

空间优化：一维数组解法

可以将空间复杂度从 O(n×W) 降到 O(W)，使用一维数组从后往前更新：

function knapsackOptimized(weights, values, capacity) {
  const dp = Array(capacity + 1).fill(0);
<p>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]);
}
}</p><p>return dp[capacity];
}</p>

基本上就这些。掌握状态定义和转移方程是关键，理解后可扩展到完全背包等问题。

以上就是J*aScript动态规划_背包问题解决方案的详细内容，更多请关注其它相关文章！