动态规划算法之背包问题

动态规划

动态规划（Dynamic Programming，简称 DP）是一种解决最优化问题的方法。它通过将问题分解为多个子问题，存储每个子问题的解，避免重复计算，从而提高计算效率。动态规划通常适用于那些可以通过“重叠子问题”和“最优子结构”来优化的问题。

动态规划的基本思想

1. 最优子结构：一个问题的最优解可以由子问题的最优解推导出来。
2. 重叠子问题：同一子问题被多次求解。动态规划的一个关键思想是通过存储中间结果来避免重复计算。

动态规划的三大要素

1. 状态定义：定义一个状态表示子问题的解。
2. 状态转移方程：通过已知的子问题的解，推导出当前问题的解。
3. 边界条件：确定初始状态。

动态规划的解题步骤

1. 确定状态：首先需要定义一个状态，它通常是一个数组或矩阵，用于存储子问题的解。
2. 确定状态转移方程：定义如何根据子问题的解来得到当前问题的解。
3. 计算结果：利用已定义的状态转移方程，从边界条件开始，逐步计算并得到最终解。

示例：斐波那契数列

斐波那契数列的定义是：F(0) = 0, F(1) = 1, 且对于所有 n >= 2，F(n) = F(n-1) + F(n-2)。

我们可以使用动态规划来解决这个问题。动态规划的关键是避免重复计算，特别是对于相同的子问题。

动态规划实现斐波那契数列的 JS 代码

function fibonacci(n) {
  // 定义状态数组
  let dp = new Array(n + 1);
  
  // 边界条件
  dp[0] = 0;
  dp[1] = 1;
  
  // 状态转移方程
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  
  return dp[n];
}

console.log(fibonacci(10)); // 输出 55
Copy

解释

1. 状态定义：我们用数组 dp 来存储每一个斐波那契数值，dp[i] 表示第 i 个斐波那契数。
2. 状态转移方程：dp[i] = dp[i - 1] + dp[i - 2]，这是根据斐波那契数列的定义推导出来的。
3. 边界条件：我们设定 dp[0] = 0 和 dp[1] = 1，这是斐波那契数列的起始值。

通过动态规划方法，我们避免了重复计算，例如对于 fibonacci(10)，我们没有重复计算 fibonacci(5)，因为它已经在数组中存储。

背包问题

背包问题（Knapsack Problem）是动态规划中一个非常经典的问题，涉及到最优化问题。在这个问题中，我们需要在给定的背包容量限制下，选择一些物品，使得它们的总价值最大。

背包问题的两种经典类型

1. 0/1 背包问题（0/1 Knapsack Problem）

   • 在这种问题中，每个物品只能选择一次，或者放进背包，或者不放进背包。

2. 分数背包问题（Fractional Knapsack Problem）

   • 这个问题允许我们将物品分割成更小的部分进行选择。例如，如果物品的重量和价值可以按比例选择（例如按物品的重量比例取价值的一部分），我们可以选择物品的某一部分。

0/1 背包问题

0/1 背包问题通常是动态规划问题中非常经典的一个。其目标是在背包的容量 W 限制下，选择物品，使得物品的总价值最大。

问题描述

• 给定 n 个物品，每个物品都有一个重量和一个价值。
• 背包的容量为 W。
• 要选择哪些物品放入背包，以使得它们的总重量不超过 W，且总价值最大。

解决方案：动态规划

1. 状态定义

我们用 dp[i][w] 来表示前 i 个物品中，能放入容量为 w 的背包中的最大价值。

• i 表示当前考虑的物品数量（从 1 到 n）。
• w 表示背包的当前容量（从 0 到 W）。

2. 状态转移方程

对于每个物品 i 和每个容量 w，我们有两个选择：

1. 不将第 i 个物品放入背包，这时最大价值就是 dp[i-1][w]，即不放这个物品时的最大价值。
2. 将第 i 个物品放入背包，此时最大价值是 dp[i-1][w-weights[i-1]] + values[i-1]，即在背包剩余容量 w-weights[i-1] 下，放入物品 i 后的最大价值。

最终的状态转移方程是：

[ dp[i][w] = \max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1]) ]

3. 边界条件

• 当没有物品时，所有的背包容量 w 的最大价值为 0：dp[0][w] = 0。
• 当背包容量为 0 时，不管有多少物品，背包中的最大价值为 0：dp[i][0] = 0。

0/1 背包问题的完整代码

function knapsack(values, weights, W) {
  let n = values.length;
  let dp = Array(n + 1).fill().map(() => Array(W + 1).fill(0));

  // 遍历每个物品
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= W; 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][W]; // 返回最大价值
}

// 示例数据
let values = [60, 100, 120];
let weights = [10, 20, 30];
let W = 50;

console.log(knapsack(values, weights, W));  // 输出 220
Copy

代码解释

1. 状态数组初始化：我们定义一个二维数组 dp[i][w] 来存储每个子问题的解。dp[i][w] 表示前 i 个物品在容量为 w 的背包中的最大价值。初始化时，所有的 dp[i][w] 都设置为 0，因为当没有物品或背包容量为 0 时，最大价值为 0。

2. 循环遍历物品和背包容量：

   • 外层循环遍历每个物品 i，从第一个物品到最后一个物品。
   • 内层循环遍历每个背包容量 w，从 1 到 W。

3. 状态转移：

   • 如果当前物品的重量 weights[i-1] 小于等于当前背包容量 w，我们就有两个选择：放入物品 i 或不放。
   • 如果不放物品 i，最大价值就是 dp[i-1][w]（即之前已经计算的解）。
   • 如果放入物品 i，最大价值是 dp[i-1][w-weights[i-1]] + values[i-1]，即在剩余的背包容量下，添加物品 i 的价值。

4. 结果：dp[n][W] 即为我们需要的答案，表示在容量为 W 的背包中，前 n 个物品的最大价值。

示例分析

考虑以下例子：

• 物品的价值：[60, 100, 120]
• 物品的重量：[10, 20, 30]
• 背包容量：50

动态规划的最终解就是在背包容量为 50 的情况下，选择物品使得总价值最大。通过状态转移方程的计算，最终结果是 220，即选择物品 2 和物品 3（分别有价值 100 和 120），总重量为 50，总价值为 220。

总结

1. 背包问题的核心思想是通过决策每个物品是否放入背包，从而构造一个子问题的解。动态规划帮助我们保存每个子问题的结果，避免重复计算。
2. 0/1 背包问题常用于决策类最优化问题，特别是在有限资源的情况下选择物品，使得价值最大。

背包可视化理解