01背包问题
-
问题定义
· 有 n 个物品，每个物品 i 有一个重量 w[i] 和价值 v[i]
· 给定一个容量为 C 的背包
· 每个物品只能选一次（0 或 1），目标是让背包内物品总价值最大 -
动态规划状态定义
二维 DP：
dp[i][j] 表示考虑前 i 个物品，背包容量为 j 时能获得的最大价值。
转移方程：
dp[i][j] = max( dp[i-1][j] , dp[i-1][j - w[i]] + v[i] )
· 不选第 i 个物品 → dp[i-1][j]
· 选第 i 个物品（前提 j ≥ w[i]） → dp[i-1][j-w[i]] + v[i]
边界：dp[0][j] = 0（0 个物品时价值为 0）
最终答案：dp[n][C] -
空间优化（一维滚动数组）
观察发现 dp[i][j] 只依赖于 i-1 行的数据，因此可以降为一维数组 dp[j]。
关键：内层循环必须倒序遍历容量，避免同物品被重复使用。
def knapsack_01(weights, values, C):
n = len(weights)
dp = [0] * (C + 1)
for i in range(n):
# 倒序保证每个物品只选一次
for j in range(C, weights[i] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[C]
-
例子
· n = 3, C = 5
· 物品1：(w=2, v=4)
· 物品2：(w=3, v=5)
· 物品3：(w=4, v=6)
二维 DP 计算后最优解为：选物品1+物品2，总重5，总价值9。 -
复杂度
· 时间：O(n * C)
· 空间：O(C)（优化后） -
如何回溯找出选了哪些物品？
可以用二维 dp 记录选择路径，或额外记录一个 choice[i][j] 数组。常见做法：从 dp[n][C] 倒推，如果 dp[i][j] == dp[i-1][j] 说明没选 i，否则选了 i 并令 j -= w[i]。