Javascript动态规划算法——背包问题（01背包）

01 背包问题（0/1 Knapsack Problem）是一个经典的动态规划问题，旨在从一组物品中选取若干个物品放入背包中，使得背包中物品的总价值最大，且背包的总重量不超过给定的限制。

问题描述：

• 有一组物品，每个物品有一个重量和价值。
• 背包有一个最大承重能力。
• 每个物品只能选择一次（即 0/1 背包），问题是选择哪些物品使得背包中的总价值最大，且不超过背包的最大承重。

输入：

• n：物品的数量。
• W：背包的最大承重。
• w[i]：第 i 个物品的重量。
• v[i]：第 i 个物品的价值。

输出：

• 背包能承载的最大总价值。

解决思路：

动态规划是解决这个问题的一个常用方法。我们使用一个二维数组 dp[i][w] 来表示前 i 个物品放入最大重量为 w 的背包时，能够得到的最大价值。然后通过递推公式来更新这个数组。

递推公式：

• 选择第 i 个物品：如果选择第 i 个物品，我们的目标是使得 dp[i-1][w - w[i]] 加上物品的价值 v[i]。
• 不选择第 i 个物品：如果不选择第 i 个物品，那么就是 dp[i-1][w]。

所以状态转移方程为：
[ dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i]] + v[i]) ]
这表示在考虑第 i 个物品时，我们要么不选择它（dp[i-1][w]），要么选择它（dp[i-1][w - w[i]] + v[i]）。

动规五部曲

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

代码实现（二维数组）：

const w = [1, 4, 3]; // 物品重量  
const value = [1500, 3000, 2000]; // 物品的价值  
const m = 4; // 背包容量  
const n = 3; // 物品的个数  
  
// 二维数组v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值  
let v = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));  
  
// 遍历物品和背包容量  
for (let i = 1; i <= n; i++) {  
  for (let j = 1; j <= m; j++) { 
  //w[i-1] [1,4,3]1索引为0但对应着第一个物品的价值 
    if (w[i-1] > j) {  
      v[i][j] = v[i - 1][j];  
    } else {  
      v[i][j] = Math.max(v[i - 1][j], value[i - 1] + v[i - 1][j - w[i - 1]]);  
    }  
  }  
}  
  
console.log(v[n][m]); // 输出最大价值

动态规划的空间优化：

由于每次计算 dp[i][w] 只与 dp[i-1][w] 和 dp[i-1][w - w[i]] 有关，因此我们只需要使用一个一维数组来优化空间复杂度。

代码实现（一维数组）☆☆☆：

//二维数组压成一维
// dp[i]表示容量为i的背包，所背物品最大价值
function bag1(weights, values, W){
    const n = weights.length;
    const dp = new Array(W + 1).fill(0);
    for (let i = 0; i < n; i++) {
        //遍历直至背包容量小于物品容量 j >= weights[i]
        for (let j = W; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
        //console.log(dp)
    }
    //console.log(dp)
    return dp[W];
}
bag1(w,value,bagW);

1.明白d[i]含义，为背包容量为i时能装的最大价值 （dp[i]表示容量为i的背包，所背物品最大价值）
2.注意遍历顺序！！！：先遍历物品再遍历背包，背包从后往前遍历（否则会出现将同一个物品放入多次情况）

时间和空间复杂度：

• 时间复杂度：O(n * W)，其中 n 是物品的数量，W 是背包的最大承重。每个物品遍历背包的每个容量值。
• 空间复杂度：O(W)，由于我们使用了一维数组来保存背包的最大价值。

示例运行：

对于输入：

• values = [60, 100, 120]
• weights = [10, 20, 30]
• capacity = 50

输出是：

220

这表示，在背包容量为 50 的情况下，选择物品 2 和物品 3，总价值是 220。

总结：

01 背包问题的动态规划解法通过递推和状态转移来逐步计算每个可能的背包容量下的最大价值。通过优化空间复杂度，我们能够有效地使用一维数组来存储当前状态，并提高算法的执行效率。