跳到主要内容

背包模型

本节目标

从选择次数和状态层来源判断背包转移、初始化与容量遍历方向。

背包题把每个候选写成 (v, w)：v 表示体积，w 表示价值；多重背包再加入数量 s。先问每件能选几次，再决定状态和循环方向。

识别信号​

  • 有统一容量、金额或目标和；每个候选消耗资源并产生价值、可达性或方案数。
  • 题目明确每件至多一次、可无限次，或有有限数量上限。
  • dp[j] 可以表示容量不超过或恰好为 j 时的最优值、可达性或计数。

状态定义与转移推导​

01 背包的二维状态为 dp[i][j]：前 i 件物品在容量 j 内的最大价值。第 i 件 (v, w) 不选时来自 dp[i-1][j]，选时来自 dp[i-1][j-v]+w。两项都读上一层，因此每件最多一次。

压缩后写作 dp[j] = max(dp[j], dp[j-v] + w)。完全背包选择项来自本层，正序更新让当前物品可以继续使用；多重背包则枚举 1..s 件后仍从上一层读取。可达性以 dp[0]=true 初始化，组合计数以 dp[0]=1 初始化。

初始化与遍历顺序​

最大价值的“容量不超过”状态全设为 0。01 背包容量从大到小：更新 j 时 j-v 尚未在本轮更新，仍代表上一物品层。完全背包容量从小到大：j-v 已可代表本轮状态，因而允许重复。组合数还要让硬币在外层，避免把不同选择顺序重复计数。

通用模板​

dp[0..m] = 0
for (v, w) in items:
    for j = m down to v:      # 01 背包
        dp[j] = max(dp[j], dp[j-v] + w)

for (v, w) in items:
    for j = v to m:           # 完全背包
        dp[j] = max(dp[j], dp[j-v] + w)

核心函数只消费准备好的 (v, w) 或 (v, w, s)。01 背包中，C++ 的 maxValue() 使用全局的 m 和 items，Python 的 max_value(m, items) 接受这两个准备好的参数，并返回 dp[m]。两种实现的 main 都只负责读取输入、调用核心函数、输出答案。

空间优化与复杂度​

二维 O(nm) 状态只依赖相邻物品层时可压为 O(m)。01 与完全背包的时间均为 O(nm)；直接枚举数量的多重背包为 O(m Σs)，适合作为理解有限选择的基线。

母题序列​

  1. 01 背包问题 必学：倒序读取上一层状态。
  2. 完全背包问题 必学：正序读取本层状态。
  3. 分割等和子集 必学：把最大价值改为布尔可达性。
  4. 零钱兑换 必学：区分最少数量。
  5. 零钱兑换 II 必学：组合计数。
  6. 多重背包问题 I 拓展：在数量上限内枚举选择。

常见误区​

  • 把 (v, w) 写成价值、体积，导致转移和输入语义同时颠倒。
  • 01 背包正序循环，意外重复使用当前物品。
  • 组合计数把金额放外层，计算成排列数。
  • 可达性或恰好装满状态沿用“全零就是可行”的最大价值初始化。

迁移方向​

目标改为最小代价时换成无穷大初始化；目标是恰好装满时明确不可达状态。数量很大时再学习二进制拆分等优化，但先用状态来源证明循环方向。