动态规划背包问题 3 大核心变种（01/完全/多重）状态转移方程与遍历顺序深度解析

动态规划背包问题 3 大核心变种（01/完全/多重）状态转移方程与遍历顺序深度解析

背包问题是动态规划领域的经典模型，其变种在实际算法面试与竞赛中出现的频率极高。本文将彻底拆解01背包、完全背包、多重背包三大核心变种的内在联系与本质区别，通过对比状态转移方程与遍历顺序的差异，帮助读者建立系统性的解题思维框架。

1. 背包问题基础模型与核心思想

背包问题的基本场景是：给定一个容量为V的背包和N个物品，每个物品有重量w和价值v，如何选择物品装入背包使得总重量不超过V且总价值最大。根据物品选取规则的不同，主要分为三种变体：

• 01背包：每件物品最多选一次（选/不选）
• 完全背包：每件物品可以选无限次
• 多重背包：每件物品有明确的次数限制

动态规划解背包问题的核心在于状态定义与状态转移。我们通常定义dp[i][j]表示考虑前i件物品，在背包容量为j时能获得的最大价值。状态转移的关键在于物品选取策略如何影响状态更新。

重要观察：三种背包问题的差异仅体现在状态转移方程的第二项（选取物品时的转移方式）

2. 01背包：逆向遍历的数学原理

01背包是最基础的背包模型，其状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

当使用一维数组优化空间时，必须逆向遍历背包容量：

for i in range(1, n+1): for j in range(V, w[i]-1, -1): # 从大到小遍历 dp[j] = max(dp[j], dp[j-w[i]] + v[i])

逆向遍历的数学本质：

• 确保状态转移时使用的dp[j-w[i]]是上一轮计算的结果（即i-1时的状态）
• 如果正向遍历，dp[j-w[i]]可能已经被本轮更新，导致同一物品被多次选取

3. 完全背包：正向遍历的必然性

完全背包的状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])

一维数组实现时需要正向遍历：

for i in range(1, n+1): for j in range(w[i], V+1): # 从小到大遍历 dp[j] = max(dp[j], dp[j-w[i]] + v[i])

正向遍历的合理性证明：

1. dp[i][j-w[i]]需要先于dp[i][j]计算
2. 正向遍历时，dp[j-w[i]]已经是考虑过当前物品i的状态
3. 这与完全背包的无限选取特性完美契合

4. 多重背包：二进制优化的艺术

多重背包的状态转移方程为：

dp[i][j] = max(dp[i-1][j-k*w[i]] + k*v[i]) for k in 0..min(m[i], j/w[i])

直接实现的时间复杂度为O(NVK)，通过二进制拆分优化可降为O(NVlogK)：

# 二进制拆分过程 index = 0 for i in range(1, n+1): k = 1 while k <= m[i]: weight[index] = w[i] * k value[index] = v[i] * k m[i] -= k k *= 2 index += 1 if m[i] > 0: weight[index] = w[i] * m[i] value[index] = v[i] * m[i] index += 1 # 转化为01背包问题 for i in range(index): for j in range(V, weight[i]-1, -1): dp[j] = max(dp[j], dp[j-weight[i]] + value[i])

5. 三大变种对比与决策树分析

通过下表可以清晰对比三种背包问题的核心差异：

决策树视角的理解：

• 01背包：每个物品是二叉树选择（选/不选）
• 完全背包：每个物品是多叉树选择（选0次、1次...直到放不下）
• 多重背包：每个物品是受限多叉树选择（选0次到m[i]次）

6. 混合背包的通用处理框架

当问题中同时存在三种背包变种时，可以统一处理：

for i in range(1, n+1): if is_01_pack(item[i]): # 01背包处理 for j in range(V, w[i]-1, -1): dp[j] = max(dp[j], dp[j-w[i]] + v[i]) elif is_complete_pack(item[i]): # 完全背包处理 for j in range(w[i], V+1): dp[j] = max(dp[j], dp[j-w[i]] + v[i]) else: # 多重背包处理 # 二进制拆分后按01背包处理 k = 1 while k <= m[i]: for j in range(V, k*w[i]-1, -1): dp[j] = max(dp[j], dp[j-k*w[i]] + k*v[i]) m[i] -= k k *= 2 if m[i] > 0: for j in range(V, m[i]*w[i]-1, -1): dp[j] = max(dp[j], dp[j-m[i]*w[i]] + m[i]*v[i])

7. 常见误区与调试技巧

易错点警示：

1. 混淆遍历方向导致错误状态转移
2. 多重背包未优化导致超时
3. 边界条件处理不当（特别是j<w[i]的情况）

调试建议：

• 打印dp表观察状态变化
• 小规模数据手工验证
• 检查物品索引是否从1开始

# 调试打印示例 def print_dp(dp, V): print("Current DP array:") for j in range(V+1): print(f"{dp[j]:2}", end=" ") print()

掌握背包问题的核心在于理解状态转移的本质差异，通过大量练习培养对遍历顺序的直觉判断能力。建议从LeetCode 416（分割等和子集）、322（零钱兑换）等经典题目入手实践。