02_Knapsack DP 背包DP
背包 DP
背包问题简介
背包问题通常涉及将有限容量的容器用物品的子集填满，我们希望计算或优化与物品相关的某些数量。几乎每次，你可以将每个物品视为具有正重量，而我们选择的物品的总重量不得超过容器的容量，这个容量是一个数字。
背包问题的变体
- 0/1 背包问题: 选择物品的子集，使得它们总价值最大化，且总重量不超过容器容量
- 完全背包问题: 找到所有可能的、由任何物品子集实现的总重量，这些总重量不超过容器容量
- 计数问题: 计算有多少种物品序列能够完全填满容器，这意味着总重量正好等于容器的容量（顺序可能重要也可能不重要）
提示: 背包问题的动态规划解法通常包含一个状态来跟踪背包的容量，状态转移涉及尝试将一个物品添加到背包中。在竞赛编程中，你可以预期经典背包问题会被赋予变化、伪装和额外的状态信息。
示例 - 骰子组合 (Dice Combinations)
Focus Problem: 在继续之前，请尽力解决这个问题！
题目描述
问题要求我们计算有多少种骰子投掷序列，使得顶面的和为 $N$（$N \le 10^6$）。为了与背包问题类比，这意味着我们有无限数量的重量为 $1$ 到 $6$ 的物品，并且我们想要计算有多少种物品序列，使得如果我们按照序列将物品放入容器中，容器会完全填满。请注意，在这个问题中物品的顺序是重要的。
解法
时间复杂度: $O(N)$
设 $dp[x]$ 为掷骰子得到的和为 $x$ 的所有序列的数量。要计算和为 $N$ 的序列数量，或者说找到 $dp[N]$，我们可以看看最后一个掷骰子的结果，使得总和达到 $N$。
如果最后一个掷骰子的结果是 $1$，那么我们知道当最后一个掷骰子的结果是 $1$ 时，有 $dp[N-1]$ 种方法可以得到和为 $N$。如果最后一个掷骰子的结果是 $2$，那么我们知道当最后一个掷骰子的结果是 $2$ 时，有 $dp[N-2]$ 种方法可以得到和为 $N$。继续用这种逻辑处理所有骰子数值直到 $6$。考虑所有这些情况，我们得到：
应用在一般 $x$ 上：
从基础情况 $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$，后续所有计算都会出错
dp = [1]
for i in range(int(input())):
dp.append(sum(dp[-6:]) % (10**9 + 7))
print(dp[-1])代码详细解释
这是什么问题？
这是一个爬楼梯问题的变体：每次可以走 1~6 步，求到达第 n 级楼梯有多少种走法。
逐步分析
假设输入 n = 7：
dp[0] = 1 (只有一种方式：不动)
i=1: dp[1] = sum(dp[-6:]) = dp[0] = 1
i=2: dp[2] = sum(dp[-6:]) = dp[0] + dp[1] = 1 + 1 = 2
i=3: dp[3] = sum(dp[-6:]) = dp[0] + dp[1] + dp[2] = 1 + 1 + 2 = 4
i=4: dp[4] = sum(dp[-6:]) = dp[0] + ... + dp[3] = 1 + 1 + 2 + 4 = 8
i=5: dp[5] = sum(dp[-6:]) = 1 + 1 + 2 + 4 + 8 = 16
i=6: dp[6] = sum(dp[-6:]) = 1 + 1 + 2 + 4 + 8 + 16 = 32
i=7: dp[7] = sum(dp[-6:]) = dp[1] + dp[2] + ... + dp[6] = 1 + 2 + 4 + 8 + 16 + 32 = 63状态转移方程
含义：到达第 i 级楼梯，可以从 i-1, i-2, …, i-6 任一级跳过来。
为什么取最后 6 个？
dp[-6:] 表示最后 6 个元素，即 dp[i-6] ~ dp[i-1]
sum(dp[-6:]) # 等价于 dp[i-1] + dp[i-2] + ... + dp[i-6]取模原因
10**9 + 7 是常见的模数，防止结果溢出（因为数字可能非常大）。
总结
| 部分 | 含义 |
|---|---|
dp[0] = 1 |
基础情况：0 级台阶有 1 种走法（不走） |
| 每次 +6 | 每次可以走 1~6 步 |
% (10**9+7) |
取模防溢出 |
dp[-1] |
第 n 级的答案 |
0/1 背包问题
问题描述
有 $N$ 件物品，每件物品有重量 $w_i$ 和价值 $v_i$，求在不超过背包容量 $W$ 的情况下，选择物品使得总价值最大。
解法
定义 $dp[i][j]$ 为考虑前 $i$ 件物品，背包容量为 $j$ 时的最大价值。
状态转移方程：
- 不选第 $i$ 件物品：$dp[i][j] = dp[i-1][j]$
- 选第 $i$ 件物品：$dp[i][j] = dp[i-1][j-w_i] + v_i$
代码实现
# 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])空间优化
由于每行只依赖上一行，可以使用一维数组：
# 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 中，内层循环需要倒序遍历，以确保每个物品只被使用一次。
完全背包问题
问题描述
有 $N$ 种物品，每种物品有重量 $w_i$ 和价值 $v_i$，每种物品可以使用无限次，求在不超过背包容量 $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$ 种物品，每种物品有重量 $w_i$、价值 $v_i$ 和数量 $c_i$，求在不超过背包容量 $W$ 的情况下，选择物品使得总价值最大。
二进制优化
将数量 $c_i$ 拆分成 $1, 2, 4, 8, \dots$ 的物品件数，转化为 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 背包 | 倒序 |