背包问题 (0-1 Knapsack)

算法

背包问题是一个经典的动态规划问题,给定一组物品,每种物品都有自己的重量和价值,在限定的总重量内,选择若干物品使得物品的总价值最大化。

时间复杂度:最佳 O(n×W) | 平均 O(n×W) | 最差 O(n×W)
空间复杂度:O(n×W)

应用场景/前提条件

  • 动态规划
  • 决策问题
  • 最优化理论

算法讲解

背包问题(动态规划)

介绍

背包问题(Knapsack Problem)是一类经典的组合优化问题,基本形式是:给定一组物品,每个物品有自己的重量和价值,在限定的总重量内,选择总价值最大的物品。

问题定义

最常见的背包问题是0-1背包问题(0-1 Knapsack Problem):有n个物品,第i个物品的重量为w[i],价值为v[i]。现有一个容量为W的背包,问如何选择物品放入背包,在物品总重量不超过背包容量的前提下,物品总价值最大。这里的"0-1"表示每个物品要么完整地放入背包(选择1),要么不放入背包(选择0),不能只放入一个物品的部分或放入多次。

除了0-1背包问题外,还有完全背包问题(物品可重复选择)、多重背包问题(每种物品有数量限制)和分数背包问题(物品可部分选择)等变种。

动态规划是解决背包问题的经典方法,通过构建状态转移方程,可以在伪多项式时间O(n×W)内求解这类NP完全问题(运行时间与容量W的数值成正比,而不是与W的二进制位数成多项式关系)。

算法步骤

以0-1背包问题为例,基于动态规划的解决步骤如下:

  1. 定义状态:dp[i][j]表示考虑前i个物品,背包容量为j时的最大价值
  2. 初始化:
    • dp[0][j] = 0(没有物品时,最大价值为0)
    • dp[i][0] = 0(背包容量为0时,最大价值为0)
  3. 状态转移方程:
    • 如果第i个物品的重量w[i]大于当前背包容量j,则无法放入背包:

...