BISHI136. 【模板】01背包
题目描述
你有一个背包，最大容量为 V。现有 n 件物品，第 i 件物品的体积为 w[i]、 价值为 v[i]。研究人员提出以下两种装填方案：
- 不要求装满背包，求能获得的最大总价值；
- 要求最终恰好装满背包，求能获得的最大总价值。若不存在恰好装满的 装法，则答案记为 0。
输入格式
第一行输入两个整数 n 和 V，分别表示物品数量与背包容量。 此后 n 行，第 i 行输入两个整数 w[i] 和 v[i]，分别表示第 i 件物品的体积与价值。
输出格式
输出两行：第一行输出方案 1 的答案；第二行输出方案 2 的答案（若无解输出 0）。
示例
示例 1
输入：
3 5
2 10
4 5
1 4
输出：
14
9
说明： 选择第 1、3 件物品可得最大价值 10 + 4 = 14（未装满）； 选择第 2、3 件物品时体积 4 + 1 = 5 恰好装满，价值 5 + 4 = 9。
示例 2
输入：
3 8
12 6
11 8
6 8
输出：
8
0
说明： 装第三件物品时总价值最大（8）但不满；恰好装满背包无解，输出 0。
解题思路
第一步：理解问题本质
01 背包：每件物品只有「选」或「不选」两种状态，选了的物品体积之和 不能超过容量 V，求价值之和的最大值。两问的唯一区别是方案 2 要求 体积之和恰好等于 V。
第二步：二维 DP
设 dp[i][j] 表示「前 i 件物品、容量 j 下能获得的最大价值」：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
答案是 dp[n][V]。正确但空间 O(n·V)。
第三步：滚动数组压成一维（最优）
观察转移只用到「上一行」的数据，可以把第一维去掉。 但此时内层容量必须从大到小遍历：
for j in range(V, w - 1, -1):
dp[j] = max(dp[j], dp[j - w] + v)
倒序保证 dp[j-w] 用的是「还没放第 i 件物品」时的旧值；
如果正序遍历，dp[j-w] 可能已经被本轮更新过，就会把同一件物品
用多次，变成完全背包。
第四步：两问的差异只在初值
- 不要求装满：
dp全部初始化为 0。「容量 j 装不满」也是合法状态，价值为 0。 - 恰好装满：只有
dp[0] = 0，其余初始化为-∞（表示不可达）。 这样只有能一步步从 0 转移过来的容量才有意义；最终dp[V]仍为-∞就说明装不满，按题意输出 0。
完整代码实现
算法可视化 · 逐帧回放这道题的代码67 帧 · 录制输入
import sys
NEG = float('-inf')
def solve() -> None:
"""01 背包：分别求「不必装满」与「恰好装满」的最大价值"""
data = sys.stdin.read().split()
if not data:
return
idx = 0
n = int(data[idx]); V = int(data[idx + 1]); idx += 2
items = []
for _ in range(n):
w = int(data[idx]); v = int(data[idx + 1]); idx += 2
items.append((w, v))
# 方案一：不要求装满
dp1 = [0] * (V + 1)
# 方案二：恰好装满（-inf 表示该容量尚不可达）
dp2 = [NEG] * (V + 1)
dp2[0] = 0
for w, v in items:
for j in range(V, w - 1, -1): # 倒序：保证每件物品只用一次
dp1[j] = max(dp1[j], dp1[j - w] + v)
if dp2[j - w] != NEG:
dp2[j] = max(dp2[j], dp2[j - w] + v)
ans1 = dp1[V]
ans2 = dp2[V] if dp2[V] != NEG else 0
sys.stdout.write(f"{ans1}\n{ans2}\n")
if __name__ == "__main__":
solve()
示例推演
以示例 1（容量 5，物品 (2,10)、(4,5)、(1,4)）为例，方案二 dp2 随物品更新：
| 物品 | dp2[0] | dp2[1] | … | dp2[4] | dp2[5] | 说明 |
|---|---|---|---|---|---|---|
| 初始 | 0 | -∞ | … | -∞ | -∞ | 只有容量 0 可达 |
| (2,10) | 0 | -∞ | … | -∞ | -∞ | 体积 2 → 10 |
| (4,5) | 0 | -∞ | … | 5 | -∞ | 体积 4 → 5 |
| (1,4) | 0 | 4 | … | 9 | 9 | 4+1 → 9，恰好装满 5 |
最终 dp2[5] = 9。方案一 dp1[5] = 14（选 1、3 号）。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 二维 DP | O(n·V) | O(n·V) | 直观 |
| 一维滚动 | O(n·V) | O(V) | 推荐，本题要求 |
易错点总结
1. 内层容量写成正序
正序会让同一件物品被反复使用，答案偏大 —— 这是 01 背包最经典的错误。
务必 for j in range(V, w-1, -1)。
2. 恰好装满的初值
方案二必须用 -∞ 初始化，否则「凑不出恰好 V」会被当成有效状态而误判。
3. 两问共用一个 dp 数组
两问初值不同，不能共用；分别开 dp1、dp2 才清晰。
扩展思考
- 完全背包（每件物品可取无限次）对应内层正序遍历。
- 分组背包、多重背包都能在一维写法基础上加一层循环变形。
- 若还要输出具体选了哪些物品，需要额外记录决策路径。