0-1背包与完全背包：遍历顺序背后的秘密

引言

背包问题是动态规划中的经典问题，而0-1背包和完全背包是最基础的两个变种。很多人在学习时都会遇到这样一个困惑：为什么0-1背包必须倒序遍历容量，而完全背包必须正序遍历容量？本文将深入剖析这背后的原理，帮助你真正理解而不是死记硬背。

问题回顾

0-1背包问题

有N件物品和一个容量为V的背包，每种物品只有一件，可以选择放或不放。第i件物品的重量是w[i]，价值是v[i]。求背包能装入的最大价值。

完全背包问题

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的重量是w[i]，价值是v[i]。求背包能装入的最大价值。

核心状态转移方程

两者都使用一维DP数组dp[j]表示容量为j的背包所能装的最大价值。

0-1背包的状态转移

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

完全背包的状态转移

完全一样！是的，两者的状态转移方程在形式上完全相同。那么区别到底在哪里？

遍历顺序的奥秘

为什么0-1背包必须倒序？

假设我们正序遍历容量，对于物品i，计算过程如下：

# 错误的正序遍历foriinrange(N):# 遍历物品forjinrange(w[i],V+1):# 正序遍历容量dp[j]=max(dp[j],dp[j-w[i]]+v[i])

考虑一个具体例子：

• 背包容量V = 4
• 只有一件物品，重量w = 2，价值v = 3

正序遍历过程：

1. j = 2: dp[2] = max(dp[2], dp[0] + 3) = 3
2. j = 3: dp[3] = max(dp[3], dp[1] + 3) = 3
3. j = 4: dp[4] = max(dp[4], dp[2] + 3) = 6 ❗

发现问题了吗？在计算dp[4]时，我们使用的dp[2]已经被当前物品更新过了（从0变成了3）。这相当于在同一轮循环中，同一件物品被使用了两次，违反了0-1背包"每个物品只能用一次"的约束。

倒序遍历过程：

# 正确的倒序遍历foriinrange(N):forjinrange(V,w[i]-1,-1):# 倒序遍历容量dp[j]=max(dp[j],dp[j-w[i]]+v[i])

1. j = 4: dp[4] = max(dp[4], dp[2] + 3) = 3
2. j = 3: dp[3] = max(dp[3], dp[1] + 3) = 3
3. j = 2: dp[2] = max(dp[2], dp[0] + 3) = 3

倒序保证了在计算dp[j]时，dp[j - w[i]]还是上一轮的状态（即没有考虑当前物品的状态），从而确保每个物品只被考虑一次。

为什么完全背包必须正序？

完全背包允许同一物品使用多次，这正是我们想要的效果！

# 正确的正序遍历foriinrange(N):forjinrange(w[i],V+1):# 正序遍历容量dp[j]=max(dp[j],dp[j-w[i]]+v[i])

继续上面的例子：

1. j = 2: dp[2] = max(dp[2], dp[0] + 3) = 3
2. j = 3: dp[3] = max(dp[3], dp[1] + 3) = 3
3. j = 4: dp[4] = max(dp[4], dp[2] + 3) = 6

在j=4时，我们使用了刚刚更新过的dp[2]（已经包含了当前物品），这意味着我们可以多次使用同一物品。这正是完全背包所需要的特性。

深入理解：状态依赖关系

让我们用二维DP的视角来理解这个问题：

0-1背包的二维表示

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

当前状态只依赖于上一行（i-1）的状态。

压缩到一维后，如果我们正序遍历，dp[j - w[i]]可能会被当前行更新，破坏依赖关系。倒序遍历则确保我们使用的还是上一行的状态。

完全背包的二维表示

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

当前状态依赖于当前行（i）的较小容量状态！

压缩到一维后，我们需要dp[j - w[i]]是已经考虑过当前物品的状态，这正是正序遍历能做到的。

代码对比

0-1背包完整实现

defzero_one_pack(N,V,weight,value):dp=[0]*(V+1)foriinrange(N):forjinrange(V,weight[i]-1,-1):dp[j]=max(dp[j],dp[j-weight[i]]+value[i])returndp[V]

完全背包完整实现

defcomplete_pack(N,V,weight,value):dp=[0]*(V+1)foriinrange(N):forjinrange(weight[i],V+1):dp[j]=max(dp[j],dp[j-weight[i]]+value[i])returndp[V]

进阶思考

为什么不能交换循环顺序？

有些同学可能会想：能不能先遍历容量，再遍历物品？

对于0-1背包，如果先遍历容量，那么每个容量j都会考虑所有物品，但无法保证每个物品只使用一次，实际上变成了"每个容量下选择最优物品"的问题，不是我们想要的背包问题。

初始化细节

• 如果要求恰好装满背包：初始化dp[0]=0，其他为负无穷
• 如果只要求最大价值：初始化所有dp[j]=0

总结

1. 0-1背包倒序：防止同一物品被多次使用，保证状态转移基于上一轮结果
2. 完全背包正序：允许同一物品被多次使用，状态转移基于本轮已更新结果
3. 本质区别：状态依赖的对象不同，导致遍历顺序的差异

记住这个核心思想：遍历顺序决定了当前物品能否被重复使用。理解了这一点，你就不再需要死记硬背，而是能够根据问题的约束条件自然推导出正确的遍历顺序。

练习题推荐

1. LeetCode 416: 分割等和子集（0-1背包）
2. LeetCode 518: 零钱兑换II（完全背包）
3. LeetCode 322: 零钱兑换（完全背包）