分组背包

先看一个具体场景：有 2 组物品，一个容量 $m=6$ 的背包。组 1 里放着两件$(w,v)=(2,3),(3,4)$，组 2 里放着两件 $(2,2),(4,5)$。规则多了一条硬约束，每一组里至多挑一件（也可以一件都不挑），组与组之间互不影响。目标仍是不超重的前提下让总价值最大。

为什么不能把它当普通 01 背包，把 4 件一股脑丢进去做？因为 01 背包允许「组 1 的两件同时拿」，$(2,3)+(3,4)$ 重 5、价值 7，它会毫不犹豫地收下。可分组规则里这是非法的：同一组内互斥。 普通 01 背包压根不知道「组」的存在，自然管不住「一组只能出一件」。

那把每组「挑哪一件、或不挑」的所有搭配枚举出来呢？$g$ 组、每组约 $c$ 种选择，就是 $c^g$ 种组合， 又回到指数爆炸。分组背包的思路，是把这层组内的互斥，直接焊进背包的转移里，让「组」成为 DP 的阶段。

定状态。设 $f[g][j]$ 表示：只在前 $g$ 组里挑选（每组至多一件）、总重量不超过 $j$ 时的最大价值。 和 01 背包最大的不同在阶段的粒度：01 里一个阶段决断「第 $i$ 件取不取」，分组里一个阶段决断「第 $g$ 组，不选，还是选组内的哪一件」。

不选第 $g$ 组：本组一件都不拿，前 $g$ 组的最优就等于前 $g-1$ 组在同容量 $j$ 下的最优，即 $f[g-1][j]$。

选第 $g$ 组里的某一件 $k$（需装得下 $j\ge w_k$）：腾出 $w_k$，剩下的 $j-w_k$ 留给前 $g-1$ 组去最优，再加上这件的价值 $v_k$，即 $f[g-1][j-w_k]+v_k$。 究竟选组内哪一件？把每一件都试一遍，取最好的那件。

合起来，就是转移方程，注意第二项里那个对组内物品的 $\max$：

边界：$f[0][j]=0$（一组都不考虑，价值为 0）。答案：$f[G][m]$。 对比 01 背包 $f[i][j]=\max(f[i-1][j],\ f[i-1][j-w_i]+v_i)$，分组只是把「取这一件」换成了「在组内挑最好的一件」，多套了一层组内的 $\max$。

用开头的例子（组 1 = $(2,3),(3,4)$，组 2 = $(2,2),(4,5)$，容量 6）走几步，把方程「跑起来」，重点盯住每组只出一件：

和 01 背包一样，转移只用到上一行 $f[g-1][\cdot]$，于是可以卷成一维 $f[j]$ 就地更新。 但组内多了一层枚举，一维写法的循环套三层，顺序有讲究：

for 组 g = 1 … G:
  for j = m downto 0:        // ★容量倒序，在组内枚举之外
    for 组内每件 (w, v):
      f[j] = max( f[j], f[j − w] + v )

记住这个骨架的关键：容量循环 $j$ 必须在「组内物品枚举」的外层，而且照旧倒序。 这样一来，处理组 $g$ 时，无论组内枚举到第几件，$f[j-w]$ 用的都是本组还没动过的旧值（即上一行的值），组内各件都在「本组尚未出手」的同一起点上竞争，自然只会有一件胜出被计入。

把三重循环写反，让组内物品在外、容量 $j$ 在里：

for 组 g = 1 … G:
  for 组内每件 (w, v):        // ✗ 组内枚举跑到了外层
    for j = m downto 0:
      f[j] = max( f[j], f[j − w] + v )

这时组内每一件都各自独立地跑一遍完整的倒序背包。第一件更新完 $f[\cdot]$ 后，第二件是在「第一件已经装进去」的结果上继续做，于是同一组的两件可以被同时选中。 这恰好退化成「把这一组当作若干件各自独立的 01 物品」，组内互斥的约束彻底失效。

用开头组 1 $(2,3),(3,4)$、容量 5 验一下错法：先跑 $(2,3)$ 得 $f[5]=3$；再跑 $(3,4)$ 时 $f[5]=\max(3,\ f[2]+4)=\max(3,3+4)=7$，$f[2]=3$ 里已经含了 $(2,3)$，于是 7 = 两件相加。可正确答案（组内至多一件）只该是 $4$。一层循环放错位置，答案就从 4 涨成了 7。

道理讲完，不如让两种顺序同跑一遍并排对照。默认就是本节手算的那组：单独一组 $(2,3),(3,4)$、容量 5。 左边把容量倒序放在组内件之外，组内两件都基于「本组未动过」的旧值竞争，只有一件胜出，$f[5]=4$； 右边把容量倒序沉进组内件里层，第二件在「第一件已装进去」的结果上继续叠，两件被同时计入，$f[5]=7$。 单步走到右侧 $j=5$ 那一格，会看到来源列被标红：那正是「同组两件叠在一起」的瞬间。改改 w / v 或再加一组，看这 $4$ 与 $7$ 的差随之变化。