动态规划算法之背包问题

发布时间:2025-02-02
3822 字, 需阅读 8 分钟
已被阅读1

动态规划

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

动态规划的基本思想

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

动态规划的三大要素

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

动态规划的解题步骤

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

示例:斐波那契数列

斐波那契数列的定义是:F(0) = 0, F(1) = 1, 且对于所有 n >= 2F(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

解释

  1. 状态定义:我们用数组 dp 来存储每一个斐波那契数值,dp[i] 表示第 i 个斐波那契数。
  2. 状态转移方程dp[i] = dp[i - 1] + dp[i - 2],这是根据斐波那契数列的定义推导出来的。
  3. 边界条件:我们设定 dp[0] = 0dp[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

代码解释

  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 背包问题常用于决策类最优化问题,特别是在有限资源的情况下选择物品,使得价值最大。

背包可视化理解

作者:admin
版权声明:
本文采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
分享到: