02_Knapsack DP 背包DP
背包 DP
背包问题简介
背包问题通常涉及将有限容量的容器用物品的子集填满，我们希望计算或优化与物品相关的某些数量。几乎每次，你可以将每个物品视为具有正重量，而我们选择的物品的总重量不得超过容器的容量，这个容量是一个数字。
背包问题的变体
- 0/1 背包问题: 选择物品的子集，使得它们总价值最大化，且总重量不超过容器容量
- 完全背包问题: 找到所有可能的、由任何物品子集实现的总重量，这些总重量不超过容器容量
- 计数问题: 计算有多少种物品序列能够完全填满容器，这意味着总重量正好等于容器的容量（顺序可能重要也可能不重要）
提示: 背包问题的动态规划解法通常包含一个状态来跟踪背包的容量，状态转移涉及尝试将一个物品添加到背包中。在竞赛编程中，你可以预期经典背包问题会被赋予变化、伪装和额外的状态信息。
示例 - 骰子组合 (Dice Combinations)
题目描述
https://cses.fi/problemset/task/1633
问题要求我们计算有多少种骰子投掷序列，使得顶面的和为 N（N ≤ 106）。为了与背包问题类比，这意味着我们有无限数量的重量为 1 到 6 的物品，并且我们想要计算有多少种物品序列，使得如果我们按照序列将物品放入容器中，容器会完全填满。请注意，在这个问题中物品的顺序是重要的。
解法
时间复杂度: O(N)
设 dp[x] 为掷骰子得到的和为 x 的所有序列的数量。要计算和为 N 的序列数量，或者说找到 dp[N]，我们可以看看最后一个掷骰子的结果，使得总和达到 N。
如果最后一个掷骰子的结果是 1，那么我们知道当最后一个掷骰子的结果是 1 时，有 dp[N − 1] 种方法可以得到和为 N。如果最后一个掷骰子的结果是 2，那么我们知道当最后一个掷骰子的结果是 2 时，有 dp[N − 2] 种方法可以得到和为 N。继续用这种逻辑处理所有骰子数值直到 6。考虑所有这些情况，我们得到：
状态转移方程
dp[i] = dp[i − 1] + dp[i − 2] + dp[i − 3] + dp[i − 4] + dp[i − 5] + dp[i − 6]
从基础情况 dp[0] = 1 开始，然后 dp[1]、dp[2]、dp[3]，依此类推，可以使用递推公式计算，直到找到 dp[N]。注意在代码中，如果 x < 0 存在，我们会忽略 dp[x]。
为什么 dp[0] = 1？ - dp[0] 表示和为 0 的序列数量 - 只有一种方式得到和为 0：什么都不投 - 这是一个基准点，作为递推的起点 - 如果没有 dp[0] = 1，后续所有计算都会出错
MOD = 10**9 + 7
n = int(input())
dp = [1]
for i in range(n):
total = sum(dp[-6:])
dp.append(total % MOD)
print(dp[-1])0/1 背包问题
问题描述
有 N 件物品，每件物品有重量 wi 和价值 vi，求在不超过背包容量 W 的情况下，选择物品使得总价值最大。
解法
定义 dp[i][j] 为考虑前 i 件物品，背包容量为 j 时的最大价值。
状态转移方程： - 不选第 i 件物品：dp[i][j] = dp[i − 1][j] - 选第 i 件物品：dp[i][j] = dp[i − 1][j − wi] + vi
dp[i][j] = max (dp[i − 1][j], dp[i − 1][j − wi] + vi)
代码实现
# 0/1 背包 - 二维 DP
N, W = map(int, input().split())
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
w, v = map(int, input().split())
for j in range(W + 1):
dp[i][j] = dp[i-1][j]
if j >= w:
dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)
print(dp[N][W])详细解释
外层循环 i：遍历第 1 到 N 件物品 内层循环 j：遍历容量 0 到 W
核心逻辑（以 i=2, j=8 为例）：
假设：第 2 件物品重量 w=3，价值 v=5
dp[2][8] = max(
dp[1][8], # 不选第2件：用前1件填满8容量
dp[1][8-3] + 5 # 选第2件：前1件填剩余5容量 + 第2件价值5
)空间优化
由于每行只依赖上一行，可以使用一维数组：
# 0/01 背包 - 一维 DP（空间优化）
N, W = map(int, input().split())
dp = [0] * (W + 1)
for _ in range(N):
w, v = map(int, input().split())
for j in range(W, w - 1, -1):
dp[j] = max(dp[j], dp[j - w] + v)
print(dp[W])注意: 一维 DP 中，内层循环需要倒序遍历，以确保每个物品只被使用一次。
为什么要倒序？
原因：避免同一物品被重复使用
以物品 (w=3, v=5) 为例：
正序遍历（错误）：
for j in range(w, W + 1): # 正序
dp[j] = max(dp[j], dp[j-w] + v)假设 W=6，初始 dp=[0,0,0,0,0,0,0]
j=3: dp[3] = max(0, dp[0]+5) = 5 # 放了这个物品
j=4: dp[4] = max(0, dp[1]+5) = 5 # dp[1] 是 0
j=5: dp[5] = max(0, dp[2]+5) = 5 # dp[2] 是 0
j=6: dp[6] = max(0, dp[3]+5) = max(0, 5+5) = 10 # 出问题了！dp[3] 刚刚被更新成 5，现在 dp[6] 又去查
dp[3]，相当于同一个物品用了两次！
倒序遍历（正确）：
for j in range(W, w - 1, -1): # 倒序
dp[j] = max(dp[j], dp[j-w] + v)j=6: dp[6] = max(0, dp[3]+5) = 5 # dp[3] 还是 0（未被当前物品更新）
j=5: dp[5] = max(0, dp[2]+5) = 5 # dp[2] 还是 0
j=4: dp[4] = max(0, dp[1]+5) = 5 # dp[1] 还是 0
j=3: dp[3] = max(0, dp[0]+5) = 5 # dp[0] 是 0倒序时，大 j 先更新，小 j 后更新。大 j 用到的 dp[j-w]
还是旧值，没被当前物品污染，确保每个物品只选一次。
完全背包问题
问题描述
有 N 种物品，每种物品有重量 wi 和价值 vi，每种物品可以使用无限次，求在不超过背包容量 W 的情况下，选择物品使得总价值最大。
代码实现
# 完全背包 - 一维 DP
N, W = map(int, input().split())
dp = [0] * (W + 1)
for _ in range(N):
w, v = map(int, input().split())
for j in range(w, W + 1):
dp[j] = max(dp[j], dp[j - w] + v)
print(dp[W])注意: 完全背包中内层循环需要正序遍历，因为每种物品可以使用多次。
多重背包问题
问题描述
有 N 种物品，每种物品有重量 wi、价值 vi 和数量 ci，求在不超过背包容量 W 的情况下，选择物品使得总价值最大。
二进制优化
将数量 ci 拆分成 1, 2, 4, 8, … 的物品件数，转化为 0/1 背包问题：
# 多重背包 - 二进制优化
N, W = map(int, input().split())
items = []
for _ in range(N):
w, v, c = map(int, input().split())
k = 1
while c > 0:
take = min(k, c)
items.append((w * take, v * take))
c -= take
k *= 2
dp = [0] * (W + 1)
for w, v in items:
for j in range(W, w - 1, -1):
dp[j] = max(dp[j], dp[j - w] + v)
print(dp[W])总结
| 问题类型 | 状态转移 | 内层循环方向 |
|---|---|---|
| 0/01 背包 | dp[j] = max (dp[j], dp[j − w] + v) | 倒序 |
| 完全背包 | dp[j] = max (dp[j], dp[j − w] + v) | 正序 |
| 多重背包 | 二进制优化转为 0/01 背包 | 倒序 |