混合背包：三类物品同台

前三讲（01 背包、完全背包、多重背包）分别处理了三种基础形态。混合背包把它们放进同一道题：N 个物品分为三类——有些每件只能用一次，有些可任意件取用，有些有件数上限。它既不是纯 01，也不是纯完全，也不是纯多重。这不需要设计新算法：本讲的全部内容，就是把这道看似复杂的题拆回三个已解决的子问题，再按物品 type 分发。实际工程问题里物品几乎总是天然带类型（独占 / 共享 / 配额资源；限量品 / 散装品 / 限购品），单一类型的「纯净」背包反而是教学简化——掌握分发模式即可处理几乎所有现实背包。

1 · 三种初始直觉与为何都不通

面对「三类物品同时出现」，读者通常有三种本能反应。它们都看似合理，却各自暴露了对 DP 抽象的不同程度误解。逐一看清「为何不通」，是建立分发模式的最佳起点。

共性。三种直觉的共同病灶是：试图把「类型差异」塞进 DP 的状态空间或物品集合本身。但回看前三讲的实现，会发现状态与语义其实从未改变：

状态没变，$F[v]$ 的语义也没变——变化的只是「把这件物品纳入 F」这个动作的具体实现。

T_mixed = Σ_01 O(V) + Σ_完全 O(V) + Σ_多重 O(V·log Mᵢ)

2 · 三种背包过程

「三种初始直觉」一节的结论告诉我们：三种背包的真正差异在「如何更新 F」，而非状态空间。本讲因此把前三讲各自封装为独立过程，共享相同的接口契约：接收 F 数组与物品参数，在原地更新 F。这一「同构接口」是后续按类型分发的前提。

01 背包 · Lecture Ⅰ — ZeroOnePack(F, C, W)

for (v = V; v >= C; v--)   // 逆序
  F[v] = max(F[v], F[v-C]+W);

v 逆序 · F[v−C] 是「上层」。

完全背包 · Lecture Ⅱ — CompletePack(F, C, W)

for (v = C; v <= V; v++)   // 顺序
  F[v] = max(F[v], F[v-C]+W);

v 顺序 · F[v−C] 是「本层」。

多重背包 · Lecture Ⅲ — MultiplePack(F, C, W, M)

// 容量先耗尽 → 退化
if (C*M >= V) return CompletePack(…);
for (k of binarySplit(M))
  ZeroOnePack(F, k*C, k*W);

二进制拆分 · log Mᵢ 件 01。

2.1 · 三个过程 = 三种 transition strategy

有必要给三者一个统一命名：ZeroOnePack / CompletePack / MultiplePack 不是「三种不同的算法」，而是同一 DP 框架下的三种 transition strategy。它们共享：同一个状态空间 $F[0..V]$；同一种「加入物品后取较优」的更新逻辑 $F[v] \leftarrow \max (F[v], F[v-C]+W)$。差异仅在「加入」这个动作的合法性约束:

• 01 · 每种至多 1 次 → 逆序枚举保证 $F[v-C]$ 是「未含本物品」的上层状态；
• 完全 · 任意次数 → 顺序枚举允许 $F[v-C]$ 已含本物品；
• 多重 · 至多 Mᵢ 次 → 二进制拆分后归约为 $\log M_i$ 件 01 物品。

确认这一点后，「分发模式」的真正含义浮出水面：被分发的不是三种算法，而是同一 DP 框架下的三种 transition strategy。这把话题从「如何写代码」提到了「如何抽象 DP 的转移」——一个层级更高的位置。

2.2 · 为什么不写一个「统一」的 Pack 函数？

三个过程的接口都形如 $Pack(F, C, W, \dots )$，自然会想：写一个 Pack(F, C, W, M, type)，内部用 if 按 type 分支，不就一劳永逸？这是个合理的疑问——答案是可以，但这恰恰违背了抽象的目的。三过程的接口相同，内部语义却本质不同：

• 01 与完全的循环方向相反（v 递减 vs 递增），对 $F[v-C]$ 是「上层」还是「本层」的语义需求不同；
• 多重不仅有循环方向，还可能触发二进制拆分这一不同结构的子算法——内层根本不是单层 for 循环。

把这些异质性硬塞进同一个函数，意味着函数内部要多条 if 分支处理本不相关的语义，反而比「分别封装 + 主循环分发」更难读、更难扩展。封装为三个独立过程后，每个过程只关心自己的内层循环规则；主循环只关心「按类型选哪个过程」——这是关注点分离的具体体现。后续的分组背包（第 6 讲）、依赖背包（第 7 讲）将看到，这种封装让「加新类型」的成本始终维持在一行 dispatch。

for (const item of items) {
  switch (item.type) {
    case '01':       ZeroOnePack(F, item.C, item.W);          break;
    case 'complete': CompletePack(F, item.C, item.W);         break;
    case 'multiple': MultiplePack(F, item.C, item.W, item.M); break;
  }
}
// 完成。无任何新的 DP 推导——这正是抽象与组合的价值。

3 · 按类型分发的运行过程

F 共享的直觉。最常见的疑问是：「既然三类的循环规则不同，凭什么写到同一个 F 数组上？需不需要分别维护三个 F？」——不需要，而且这正是分发模式得以成立的关键。F 不是「01 的 DP 数组」也不是「完全的 DP 数组」——$F[v]$ 始终表示「在当前已处理的物品集合中、费用不超过 v 时的最大价值」。每次 Pack(F, item) 无论 item 哪一类，本质都是把这件物品纳入「已处理集合」。三过程的差异不在 F 的语义，而在「加入」的合法性约束（见「三种背包过程」一节）。

分发正确性 · 共同不变式。任意 Pack 过程处理完第 i 个物品后，$F[v]$ 都保持同一语义——「在已处理物品 1..i 中、按各自类型规则纳入考虑、费用不超过 v 时的最大价值」。前三讲已分别证明各过程在该语义下正确，故本讲只需依类型分发，无需就组合再作任何 DP 推导。下面单步跑混合背包：当前物品高亮，调用横幅显示它被分发到了哪个子过程、完整签名是什么（多重物品还会展开二进制拆分）,F 数组的单元按「由哪个过程更新」持久着色。

case '01':       ZeroOnePack(F, it.C, it.W);          break;
case 'complete': CompletePack(F, it.C, it.W);         break;
case 'multiple': MultiplePack(F, it.C, it.W, it.M);   break;
case 'group':    GroupPack(F, group);                 break;  // 新增一行

4 · 应用案例 · 混合券组合

「按类型分发的运行过程」一节用伪码与不变式论证了分发的正确性。下面看它在真实电商场景的落地——同一笔订单里，用户面对三类来源不同的券，每类恰好对应一种背包：店铺新客券（01，每店首单一次）、平台无门槛叠加券（完全，同种可叠加任意张）、平台限领满减券（多重，每种限领 Mᵢ 张）。三类券同台，正是开篇设想的「既不是纯 01、也不是纯完全、也不是纯多重」的混合情形。把券门槛视为费用 C、单张减免视为价值 W、购物车总额视为容量 V。拖动总额，看 DP 按券的类型采用相应件数上界——${1 / M / \lfloor V/C\rfloor}$——给出最优券组合。