Ⅵ · 分组背包 · k · v · item

分组背包：每组至多选一件

分组背包在 01 背包（第 1 讲）基础上引入一个互斥约束：物品被划分为 K 组，每组内的物品至多选取一件（组与组之间相互独立）。设第 k 组记作 $G_k$ ，组内每件物品 $j \in G_k$ 有费用 $C_j$ 与价值 $W_j$ ；在容量上限 V 下使所选物品的总价值最大。

它与 01 背包的区别仅在三层循环的嵌套顺序：外层枚举组、中层枚举容量（逆序）、内层枚举组内物品。改变这一顺序将使算法语义偏离「组内互斥」，退化为标准 01 背包。

for 每组 k: for v = V downto 0: for 组内每件 j: F[v] = max(F[v], F[v−Cⱼ] + Wⱼ)

1 · 应用案例 · 学期选课规划

每个时段构成一组，组内互斥（同一时段不能同时上多门课）。每门课 j 有学分 $C_j$ 与兴趣值 $W_j$ ，约束总学分不超过 V、目标兴趣总和最大——恰好归约为分组背包。调整学分上限，DP 给出每个时段所选课程，✓ 标记当前选中的课程。

单步推进时：外层逐组、中层容量 v 逆序、内层试遍组内每门课——每步更新一格 $F[v]$ ，同时高亮当前处理的组（金=即将写入的 $F[v]$ / 蓝=读取的父节点 $F[v-C_j]$ ）。填满后回溯出每个时段的选课方案。

记号约定 ·「前 k 组」的读法

本讲沿用以下惯例：状态 $F[k][v]$ 中的 k 是已处理组数的上界，即允许从组 $G_1, G_2, \dots , G_k$ 中各选至多一件，v 是总费用上限。k 由 0 涨到 K 对应「逐步把每组纳入候选范围」——这是正向 DP 的视角。本页采用一维滚动数组 $F[v]$ ，组的迭代由外层循环隐式承担。

选课规划的形式化归约 · 何时该用分组背包

本节的选课场景如何归约到分组背包？设有 K 个时段，每段含若干候选课程，每门课 j 有学分 $C_j$ 与兴趣值 $W_j$ ；约束为总学分不超过 V，目标为兴趣总和最大。每个时段构成一组，组内互斥——问题恰好归约为分组背包。

判别准则：

「每组至多选一件」→ 分组背包
「每件至多选一次，各物品相互独立」→ 01 背包
「每种物品至多选 M 件」→ 多重背包

关键识别点：互斥的粒度——是「件之间」还是「组之间」。若题面出现「同时段 / 同类型 / 同属性仅可选一」等表述，即可判定为分组背包，如选课的「同一时段」、套餐的「同一档位」、SKU 的「同款不同规格」等。

2 · 循环顺序的正确性 · 正确写法 vs 错误写法

两段几乎相同的代码，仅循环嵌套顺序不同——一种正确，另一种使「组内互斥」失效，退化为 01 背包。同一组数据并列对比，共享一个单步指针同步推进：左栏走正确顺序（v 外、j 内），右栏走错位顺序（j 外、v 内）。

观察右栏：同一组在多步内被反复更新，因为内层 j 不断在不同 (k, v) 写入 $F[v]$ ，把「组内多选」伪装成「组内单选」。Fill 完成后，右栏会点名哪一组发生了「组内多选」——这是 for j 错位的直接证据，其 $F[V]$ 常常虚高。

关键提醒。分组背包的关键仅在三层循环的嵌套顺序：外层枚举组、中层容量逆序、内层枚举组内物品。内层物品循环必须位于中层容量循环之内——这一行决定了组内互斥语义的成立。

转移方程与一维写法 · 形式化

引入二维状态 $F[k][v]$ ，定义为「在前 k 组中选取（每组至多一件）、总费用不超过 v 时所能取得的最大价值」。对第 k 组，决策有两类：不从该组选取，或从该组中选取某一件物品 $j \in G_k$ 。取诸种决策中的最大者：

F[k][v] = max{ F[k−1][v], max(j∈Gₖ, v≥Cⱼ)( F[k−1][v−Cⱼ] + Wⱼ ) }

答案为 $F[K][V]$ 。时间复杂度 $O(V\cdot Σ_k|G_k|) = O(NV)$ （ $N = Σ_k|G_k|$ 为全部物品总数）。沿用 01 背包的一维空间压缩， $F[k][\cdot ]$ 仅依赖 $F[k-1][\cdot ]$ ，故可用一维数组 $F[v]$ 滚动覆盖。三层循环顺序：外层组、中层容量逆序、内层组内物品。

循环错位与语义退化

「错误版」将内层与中层互换，把物品循环置于容量循环之外：同一组内的不同物品 $j_1, j_2, \dots$ 各自独立地走完一遍容量逆序循环。 $j_1$ 那一趟把「含 j₁」的方案写入 F；轮到 $j_2$ 时，读到的 $F[v-C_{j2}]$ 可能已是含 j₁ 的值，于是 $F[v] = F[v-C_{j2}] + W_{j2}$ 同时包含 j₁ 与 j₂,组内互斥约束失效。本质上，每件组内物品都被当成了独立的 01 物品。

正确顺序的语义诠释

正确写法下，对固定的 v，内层循环遍历组内全部物品， $F[v]$ 仅取这些候选（连同「不选」项）中的最大者。即在组 k 的一次处理中， $F[v]$ 至多被同组的一件物品更新——这正是「组内最多选取一件」的形式化。01 背包中「每件物品至多选取一次」的逆序循环技巧，在此被升级为「每组至多选取一件」。

组内的支配剪枝 · 实战技巧

若某组内两件物品 a, b 满足 $Ca \le Cb$ 且 $Wa \ge Wb$ ，则 b 可直接从该组剔除——同费用下 a 始终不劣于 b。这是经典「被支配物品」剪枝，在分组背包中作用范围由全部物品缩小至单一组内，工程实现中可用于预处理阶段剔除冗余候选，显著缩减内层循环规模。

作为依赖背包的基础抽象

第 7 讲的「主件 + 附件子集」约束常被转化为分组背包——把「主件 + 某一附件子集」的每种选法打包成一件复合件，同一主件下的全部复合件构成一组。组内每「件」对应一种「主件 + 附件子集」的具体选法，组内互斥即「同一主件只能采用一种附件搭配」。这是分组思想成为依赖背包基础的根本原因。

关键概念出处 · 延伸阅读

分组背包(multiple-choice knapsack problem, MCKP)在英文文献中是经典 NP-hard 整数规划问题的一支。其完整算法分类（精确解、近似解、动态规划）见 Kellerer, Pferschy, Pisinger, Knapsack Problems(Springer, 2004)第 11 章。在实际应用中，MCKP 是资源分配与套餐设计问题的核心建模工具。

通向第 7 讲 · 依赖背包

第 7 讲将引入依赖关系：某些物品的选取依赖于其他物品。届时主件与附件子集将被打包为一组，沿用本讲的分组框架，但组内物品的构造将通过先做一次 01 背包预处理完成——这一两步化归的思想是依赖背包的核心。

通向第 8 讲 · 泛化物品

分组背包同样是第 8 讲泛化物品的基础抽象：把每组看作一个价值函数 h(v) =「在该组上花费 v 所能得到的最大价值」，整个问题即对所有组的 h 做一次 (max, +) 卷积求和。本讲「每组至多选一件」的内层循环，正是计算单组 h 的一种具体形态。

3 · 应用案例 · 满减档位互斥

前面用选课规划展示了「同时段互斥」的语义，下面把分组背包套用到一个真实电商场景：用户在同一笔订单中可同时使用多张异质券，但同一档位族内的多档券彼此互斥——这是结算页「满200-30 / 满500-80 / 满1000-180 三档选一」规则的形式化。把购物车总额视为容量 V、券门槛视为费用 C、减免金额视为价值 W，每个档位族即一个互斥组，求最大总减免即标准分组背包。

滑动总额看最优组合切换：¥300 时仅服饰品类券入选（减 ¥50）;¥800 时平台主券选下档满500-80、余 ¥300 让位给服饰品类券（减 ¥130）；默认 ¥1500 时平台升至满1000-180、余 ¥500 让位给 A 店满500-70（总减 ¥250）;¥1800 时平台 + A 店 + 服饰三组联用（减 ¥300）。

为什么「满1000-180」不总是最优

读者可能直觉地认为「平台档位选最大的肯定最划算」——毕竟单张减免最高。这一直觉在预算极宽时成立，但在预算受限下常被反例打破。原因恰是分组背包的核心：跨组联用可能优于单组取最高档。取本演示数据，V = 800 为例：

仅选平台档位最大值：满1000-180 不满足门槛(800 < 1000)，退选满500-80（减 ¥80）+ 服饰满300-50（减 ¥50），总 ¥130（DP 解）;
「只选最大档」策略（若误将平台档位上限放宽）：强行单选满1000-180 不可行——直接无解;
跨组联用：满500-80（平台）+ 满300-50（服饰）= ¥130，正是 DP 给出的最优。

这一「跨组联用优于单组最高档」的现象，是分组背包在预算分配类问题（电商结算、套餐凑单、多渠道流量分配）中最有教学价值的部分——它修正「贪心式选最大」的直觉，转向「按组独立最优 + 全局联用」的二维视角。

与第 4 讲 · 混合背包的对照

第 4 讲（混合背包）演示了类型互斥：同一张券要么是 01、要么是完全、要么是多重——按 type 字段分发到不同 transition strategy。本讲（分组背包）演示的是档位互斥：同一组内的多张候选券共享同一个 transition strategy(01)，但组内最多选一张。两者都建模「互斥」，但作用粒度不同：

类型互斥 · 混合背包:「这张券属于哪种类型」——决定如何更新 $F[v]$ ;
档位互斥 · 分组背包:「这组里选哪一档」——决定从哪个候选取更新 $F[v]$ 。

在真实电商系统中，两者常并存：平台主券档位组（本组分组背包）内每张档位券都是 01 类（混合背包中的一类），再叠加平台叠加券（完全）、限领品类券（多重）。第 4 讲展示的「加 GroupPack 即可扩展」的开闭性，在工程实现中正是把本讲的 GroupPack 作为一个新分支接入第 4 讲的主循环。