0/1背包问题是组合优化领域的经典问题，核心场景是：给定一组物品，每个物品都有对应的重量和价值，同时有一个容量固定的背包，要求选择部分物品放入背包，在总重量不超过背包容量的前提下，让背包内物品的总价值达到最大，且每个物品只能选择放入或不放入，不能拆分。
0/1背包问题的数学模型
我们可以用更形式化的方式描述这个问题：假设有n个物品，背包的最大容量为W，第i个物品的重量为w[i]，价值为v[i]，其中1<=i<=n。我们需要定义一个决策变量x[i]，x[i]的取值只能是0或1，x[i]=1表示选择第i个物品，x[i]=0表示不选择第i个物品。那么问题的目标函数和约束条件如下：
- 目标函数：最大化总价值 sum(v[i] * x[i])，其中i从1到n
- 约束条件：sum(w[i] * x[i]) <= W，其中i从1到n
- 变量约束：x[i] ∈ {0,1}，其中1<=i<=n
动态规划解题思路
动态规划的核心思想是将复杂的大问题拆解为若干个相互关联的子问题，通过存储子问题的解来避免重复计算，最终得到大问题的解。对于0/1背包问题，我们可以从物品数量和背包容量两个维度定义状态。
状态定义
我们定义dp[i][c]表示考虑前i个物品，背包容量为c时，能够获得的最大总价值。其中i的取值范围是0到n，c的取值范围是0到W。
状态转移方程推导
对于第i个物品，我们有两种选择：
- 不选择第i个物品：此时最大价值等于考虑前i-1个物品、背包容量为c时的最大价值，即
dp[i][c] = dp[i-1][c] - 选择第i个物品：前提是当前背包容量c大于等于第i个物品的重量w[i]，此时最大价值等于考虑前i-1个物品、背包容量为c-w[i]时的最大价值加上第i个物品的价值v[i]，即
dp[i][c] = dp[i-1][c-w[i]] + v[i]
我们取两种选择中的最大值作为dp[i][c]的最终值，因此状态转移方程为：
当c < w[i]时，dp[i][c] = dp[i-1][c]
当c >= w[i]时，dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i])
边界条件
当没有物品可选时，也就是i=0时，无论背包容量是多少，最大价值都是0，即dp[0][c] = 0，其中0<=c<=W。
当背包容量为0时，无论有多少物品可选，都无法放入任何物品，最大价值也是0，即dp[i][0] = 0，其中0<=i<=n。
空间优化
从上面的状态转移方程可以看出，dp[i][c]的值只和dp[i-1][*]相关，和上上层及更之前的的状态没有关系，因此我们可以将二维数组优化为一维数组，减少空间占用。优化后的一维数组dp[c]表示背包容量为c时的最大价值。
需要注意的是，遍历背包容量时必须要从大到小遍历，因为如果从小到大遍历，在计算dp[c]时，dp[c-w[i]]可能已经被当前物品更新过，就会出现同一个物品被多次选择的情况，不符合0/1背包每个物品只能选一次的要求。
代码实现
我们用Python实现优化后的一维动态规划解法，代码如下：
def zero_one_knapsack(weights, values, capacity):
"""
0/1背包问题动态规划解法
:param weights: 物品重量列表，长度为n
:param values: 物品价值列表，长度为n
:param capacity: 背包最大容量
:return: 背包能装下的最大总价值
"""
n = len(weights)
# 初始化一维dp数组，长度为capacity+1，所有元素初始为0
dp = [0] * (capacity + 1)
# 遍历每个物品
for i in range(n):
# 背包容量从大到小遍历，避免重复选择当前物品
for c in range(capacity, weights[i] - 1, -1):
# 状态转移：比较不选当前物品和选当前物品的价值，取最大值
dp[c] = max(dp[c], dp[c - weights[i]] + values[i])
return dp[capacity]
# 测试用例
if __name__ == "__main__":
# 物品重量列表
weights = [2, 3, 4, 5]
# 物品价值列表
values = [3, 4, 5, 6]
# 背包容量
capacity = 8
max_value = zero_one_knapsack(weights, values, capacity)
print(f"背包容量为{capacity}时，能收集到的最大物品总价值为：{max_value}")
上面的代码中，我们首先初始化了一个长度为capacity+1的一维数组dp，所有元素初始为0。然后遍历每个物品，对于每个物品，从背包最大容量开始向下遍历到当前物品的重量，更新dp数组。最后dp[capacity]就是背包容量为capacity时的最大总价值。
复杂度分析
时间复杂度：外层循环遍历n个物品，内层循环遍历背包容量W，因此总时间复杂度为O(n*W)。
空间复杂度：使用了一维数组，长度为W+1，因此空间复杂度为O(W)。
实际场景应用
0/1背包问题的动态规划解法可以应用到很多实际场景中，比如：
- 预算有限的采购场景：每个商品有价格和收益，在总预算内选择商品最大化总收益
- 项目资源分配：每个项目需要投入资源并产生收益，在总资源有限的情况下选择项目最大化总收益
- 内存有限的缓存场景：每个缓存项有大小和访问收益，在缓存容量有限的情况下选择缓存项最大化总访问收益
只要场景符合每个物品只能选或不选、总量约束下最大化收益的特征，都可以用0/1背包的动态规划思路来求解。