动态规划进阶：背包问题与分割等和子集
背包问题，可以说是动态规划里最经典的模型之一了。我记得刚入行那会儿，面试官问我「0-1背包」和「完全背包」的区别，我支支吾吾说了半天也没讲清楚。后来在实际项目中写资源分配算法时，才真正理解了它们的精髓。
说白了，背包问题就是：给你一个容量有限的背包，和一堆有重量有价值的东西，你怎么装才能让总价值最大？
嗯，这里有两个关键变种：
- 0-1背包：每个物品只能拿一次，要么拿要么不拿
- 完全背包：每个物品可以拿无限次
你想想看，这两种场景在实际开发中太常见了。比如预算分配、任务调度、资源切割……我曾在做电商优惠券系统时，就用背包模型解决了「满减凑单」的问题。
0-1背包：状态定义与转移方程
先看0-1背包。我们定义 dp[i][j] 表示「前 i 个物品中，选出总重量不超过 j 的最大价值」。
转移方程其实就一句话：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])左边是不拿第 i 个物品，右边是拿。哪个大选哪个。
核心要点：0-1背包的遍历顺序是「先物品，后容量，容量从大到小」。为什么？因为每个物品只能用一次，从大到小遍历可以保证 dp[j - w[i]] 是上一轮的状态，不会重复使用当前物品。
我习惯用一维数组来优化空间，代码更简洁：
def zero_one_knapsack(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
# 容量从大到小遍历
for j in range(capacity, weights[i] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]个人小技巧：写0-1背包时，我总会在内层循环的边界上多检查一遍。曾经因为 range(capacity, -1, -1) 写成了 range(capacity, 0, -1)，漏掉了容量为0的情况，排查了半天……
完全背包：无限次使用的奥秘
完全背包和0-1背包的唯一区别：每个物品可以拿无限次。
你可能会想，那是不是把内层循环改成从小到大就行了？没错，就是这样。
def complete_knapsack(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
# 容量从小到大遍历
for j in range(weights[i], capacity + 1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]为什么从小到大就能无限次使用？因为当 j 从小到大遍历时，dp[j - w[i]] 可能已经被当前物品更新过了，这就相当于允许了重复选取。
我曾经踩过的坑：完全背包的「组合数」和「排列数」问题。如果求的是组合数（不考虑顺序），先遍历物品再遍历容量；如果求的是排列数（考虑顺序），先遍历容量再遍历物品。这两个顺序搞反了，结果会差很多。
经典例题：分割等和子集
这道题是0-1背包的经典应用。题目说：给你一个数组，能不能把它分成两个子集，使得两个子集的元素和相等？
说白了，就是问：能不能选出一些数，让它们的和等于总和的一半？
这不就是0-1背包吗？背包容量 = 总和的一半，每个数字的重量 = 它的值，价值也是它的值。我们只需要判断能不能恰好装满这个背包。
def can_partition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True # 容量为0时，什么都不选，肯定可以
for num in nums:
for j in range(target, num - 1, -1):
dp[j] = dp[j] or dp[j - num]
return dp[target]这里 dp[j] 表示能否凑出和为 j 的子集。初始状态 dp[0] = True，然后逐个数字往里加。
注意：这道题也可以用「位运算」优化，但面试时我更推荐用动态规划，思路清晰，不容易出错。我在实际项目中用DP版本写过资源均衡分配，稳定运行了两年多。
知识体系总览
下面这张图，是我自己总结的背包问题知识结构。每次讲给团队新人听，我都会先画一遍：
总结一下
背包问题的核心，其实就是两件事：
- 状态定义：
dp[j]表示容量为 j 时的最优值 - 遍历顺序：0-1背包容量倒序，完全背包容量正序
我在面试别人时，经常看到有人把这两个顺序搞混。其实你只要记住一句话：「倒序防重复，正序允无限」。每次写代码前默念一遍，基本不会出错。
分割等和子集这道题，是0-1背包的「恰好装满」问题。它不关心价值，只关心能不能凑出目标值。这种思路在资源分配、任务拆分中非常实用。
实战建议：如果你刚开始学背包问题，建议先手写几遍0-1背包的二维DP版本，理解清楚状态转移过程，再优化成一维。我当年就是直接跳一维，结果面试时被问到「为什么容量要倒序」直接卡壳了……
公众号:蓝海资料掘金营，微信deep3321