A背包 DP

混合背包

01/完全/多重同题

本课摘要

混合背包课程回答“01、完全和多重物品怎样共用一套转移框架”。内容以01/完全/多重同题为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

  • 判断混合背包的适用条件与状态边界
  • 围绕“01/完全/多重同题”推导转移与计算顺序
  • 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节

正在整理目录…

同一道题里，三种「件数」并存

前三类背包各自只管一种「件数」：01 背包每种恰一件、完全背包每种无限件、多重背包每种有限 mm 件。 可现实里的一道题，常常三种物品混在一起：有的只有一件、有的管够、有的限量。这就是混合背包。

×1物品 1w=2v=3恰一件×∞物品 2w=3v=4无限件×m物品 3w=4v=5有限件同一个背包容量 m=9
同一个背包，三件物品件数属性不同：物品 1 只有一件（×1）、物品 2 无限（×∞）、物品 3 限 m 件（×m），要在一次 DP 里全部装下。

先看个小例子体会一下「为什么要分派」。容量 m=9m=9，物品 1 是 01 件 (w,v)=(2,3)(w,v)=(2,3)，物品 2 是完全件 (3,4)(3,4)。 物品 1 至多拿一次，物品 2 却能反复拿。如果对它俩用同一套循环方向，必然有一个出错， 要么把只有一件的物品 1 反复塞（当成了完全），要么把管够的物品 2 也锁死成一件（当成了 01）。

难点不在「想出新方程」，混合背包没有新方程。难点在于：不同物品的件数属性不同， 必须逐件判断它属于哪一类，再套用那一类的转移方式。这份「看属性、选方式」的对照，就是这一节的主角，分派表。

状态不变，靠「循环方向」分派

状态照旧。还是那条一维滚动数组：f[j]f[j] 表示容量不超过 jj 时能取得的最大价值。 转移也照旧，就是那句熟得不能再熟的：

f[j]=max⁡(f[j], f[j−w]+v)f[j]=\max\big(f[j],\ f[j-w]+v\big)

三类物品共用这一格 f[j]f[j]、共用这一句转移。它们唯一的差别，是怎么遍历容量 jj，回想前几节反复强调的那件事：

看这件的「件数属性」就用这种转移方式01（恰一件）倒序一遍j: W → w完全（无限件）正序一遍j: w → W多重（有限件）二进制拆包后各包倒序拆成 log 个包三条路最终都写同一格：f[j] = max(f[j], f[j−w] + v)
分派表：看这件的件数属性，就用对应的转移方式，01 倒序、完全正序、多重先二进制拆包再逐包倒序。三条路最终都写同一格 f[j]。

为什么方向就能决定物种？算 f[j]f[j] 要用到 f[j−w]f[j-w]：

01（恰一件）→ 倒序（j:m→wj:m\to w）：此刻 f[j−w]f[j-w] 还没被本件动过，是「这件还没进来」的干净旧值，于是本件至多被计入一次。

完全（无限件）→ 正序（j:w→mj:w\to m）：此刻 f[j−w]f[j-w] 可能已经含了本件，于是同一件能被反复叠加，正好表达「无限次」。

多重（有限件）→ 先拆再倒序：把 mm 件二进制拆成 1,2,4,…1,2,4,\dots 与余数几个「打包件」，每个打包件当一件普通 01 物品倒序处理。 拆分保证「取 0…mm 件」的每种可能都能凑出，倒序保证每个包至多用一次，合起来就是「不超过 mm 件」。

本质 · 三类物品能同题混装，因为它们落在同一维 f[j] 上

混合背包不是一个新算法，而是前三节的拼装。既然 01、完全、多重最终都归结为同一句 f[j]=max⁡(f[j],f[j−w]+v)f[j]=\max(f[j],f[j-w]+v)， 就完全可以在同一个 f[j]f[j] 上，对每件物品按其件数属性选择遍历方向 / 是否拆包，一件件叠加处理。谁先谁后都不影响结果，因为每件都只依赖「它进来之前」的 ff。

分派的骨架长这样

把分派表落成代码，主循环就是「逐件物品，看属性走对应分支」：

for 每件物品 (kind, w, v, m):
    if kind == 01:                 // 恰一件
        for j = W downto w:        //   倒序
            f[j] = max(f[j], f[j−w] + v)
    elif kind == 完全:              // 无限件
        for j = w to W:            //   正序
            f[j] = max(f[j], f[j−w] + v)
    else kind == 多重:              // 有限 m 件
        把 m 二进制拆成若干「打包件」(cnt·w, cnt·v)
        for 每个打包件 (w', v'):
            for j = W downto w':   //   逐包倒序（当 01 物品）
                f[j] = max(f[j], f[j−w'] + v')

三条分支的循环体一字不差，区别只在 jj 的方向与多重那一步的拆包。 把它们串在一个大循环里，一维 f[j]f[j] 就地累积，处理完全部物品，f[W]f[W] 就是答案。这正是混合背包的定义式。

跟着算一遍：一件 01 + 一件完全

用开头的例子，物品 1 是 01 件 (2,3)(2,3)、物品 2 是完全件 (3,4)(3,4)，容量 8。把两件先后落到同一维 ff 上：

0
初始化。 空背包，f[0..8]=0f[0..8]=0。三类物品共用这同一条一维数组。
1
处理物品 1（01 件），倒序 j:8→2j:8\to 2：每格 f[j]=max⁡(f[j],f[j−2]+3)f[j]=\max(f[j],f[j-2]+3)，来源都是旧值 0。这一行变成 0,0,3,3,3,3,3,3,30,0,3,3,3,3,3,3,3，因为倒序，这件只被计入一次。
2
处理物品 2（完全件），正序 j:3→8j:3\to 8。到 f[6]=max⁡(3, f[3]+4)f[6]=\max(3,\ f[3]+4)，而 f[3]f[3] 此刻已被本件更新为 4，故 f[6]=4+4=8f[6]=4+4=8，同一件完全物品被叠了两次（装了 2 个），正是「无限件」想要的。
3
读答案。 继续到 f[8]=max⁡(3, f[5]+4)f[8]=\max(3,\ f[5]+4)，f[5]=7f[5]=7（= 01 件 3 + 一个完全件 4），故 f[8]=7+4=11f[8]=7+4=11。对应「01 件一个 + 完全件两个」：重 2+3+3=82+3+3=8、价值 3+4+4=113+4+4=11。01 只出一次、完全反复出，两种约束在同一维里各得其所。
j=0j=1j=2j=3j=4j=5j=6j=7j=801 后003333333完全后0034478811
同一条 f 数组的两次快照：上行是 01 件倒序处理后（每格至多含一件），下行再被完全件正序处理，高亮格为被完全件抬升的位置，f[8] 一路涨到 11。
下面的演示可以给每件物品切换件数属性（01 / 完全 / 多重），看它们在同一维 f[j]f[j] 上逐格填、每步标注「本件按哪种处理」。改改类型、w,v,mw,v,m 或容量试试。

看三类物品落进同一维 f

物品（切类型 · 改重量 / 价值 / 件数）
1
重量 w
2
价值 v
3
2
重量 w
3
价值 v
4
背包容量
m
9
三类物品共用 同一维 f[j] ：01 件倒序、完全件正序、多重件拆包后倒序。当前共展开 2 个转移单元（多重件按二进制拆分计）。
0
1
2
3
4
5
6
7
8
9
f
0
0
0
0
0
0
0
0
0
0
当前计算 依赖来源 被选转移 已确定
f[j]=0f[j]=0
初始：容量 0…9 下最大价值都是 0（空背包）。本例 物品 1 按 01（恰一件）、物品 2 按 完全（无限件），三类物品即将落到同一维 f[j] 上，各按自己的方式转移。
已暂停，第 1 步，共 17 步，1 倍速

一个统一写法：把 01 并进多重

实战里，「01」其实是「多重」的特例，恰一件，就是件数上限 m=1m=1 的多重物品（二进制拆分后只有一个 ×1\times1 包，逆序一遍，与 01 分毫不差）。 于是分派只需两条分支就够：

for 每件物品 (w, v, p):        // p = 件数：0 表示无限
    if p == 0:                 // 无限 → 完全，正序
        for j = w to W: f[j] = max(f[j], f[j−w] + v)
    else:                      // p ≥ 1（含 p==1 的“恰一件”）
        把 p 二进制拆包，各包当 01 物品逆序处理

这正是例题 P1833 樱花 的标准写法：题面用 PiP_i 编码件数，Pi=1P_i=1 是 01、0<Pi<∞0<P_i<\infty 是多重、Pi=0P_i=0 是完全。 按 PiP_i 一分派，三类樱花就在同一维 ff 上算完了。

常见陷阱 · 别把方向记反 / 别忘拆多重

混合背包最容易翻车的两处：其一，把完全件写成倒序（它就退化成 01，无限件变一件），或把 01 件写成正序（它就被反复取，答案虚高），方向必须随件数属性走。 其二，多重件忘了二进制拆分，直接当完全（正序）会超取、直接当 01（一个包倒序）会漏取。拿不准时回看 01 / 完全 / 多重 三页的方向依据。

例题

P1833樱花洛谷原生普及/提高-
题意
给定赏花起止时刻（得总时长 TT 作容量），nn 种樱花各有观赏耗时 wiw_i、美观度 viv_i 和株数 PiP_i。求 TT 时间内最大美观度。
对应关系（一题三类俱全）
件数由 PiP_i 编码：Pi=1P_i=1 → 01（恰一株）、0<Pi<∞0<P_i<\infty → 多重（有限株）、Pi=0P_i=0 → 完全（无限株）。三类落在同一维 ff 上，是混合背包定义式最标准的一题。
为什么选它
它把「按件数属性分派」摆到明面上，读入时看一眼 PiP_i 就知道走哪条分支。用「01 并进多重」的两分支统一写法最省心：Pi=0P_i=0 走完全正序，其余一律二进制拆包逆序。
转移 · 复杂度
完全支 f[j]=max⁡(f[j],f[j−wi]+vi)f[j]=\max(f[j],f[j-w_i]+v_i) 正序；有限支拆包后逐包逆序。时间 O ⁣(T⋅(n∞+∑log⁡Pi))O\!\big(T\cdot(n_\infty+\sum\log P_i)\big)。
参考代码（按 P 分派 · 两分支统一写法）
C++
在洛谷打开 P1833 
#include <iostream>
#include <algorithm>
using namespace std;

int f[1005];                 // f[j]：用时不超过 j 的最大美观度
int w2[100005], v2[100005];  // 拆分后的「打包件」（有限件走这里）
int cnt;                     // 打包件总数

int main()
{
    int sh, sm, eh, em, n;              // 起止时刻 h:m 与樱花种数
    scanf("%d:%d %d:%d %d", &sh, &sm, &eh, &em, &n);
    int T = (eh - sh) * 60 + (em - sm); // 总时长（分钟）= 背包容量

    for (int i = 1; i <= n; i++)
    {
        int w, v, p;                    // 花时间、美观度、件数上限 P
        cin >> w >> v >> p;

        if (p == 0)                     // ★P=0：无限件 → 完全背包，正序
        {
            for (int j = w; j <= T; j++)
                f[j] = max(f[j], f[j - w] + v);
        }
        else                            // ★P>0：有限 P 件 → 多重，二进制拆分成打包件
        {
            int k = 1;                  // 1,2,4,… 各捆一包，余数单独成包
            while (k < p)
            {
                cnt++;
                w2[cnt] = k * w;
                v2[cnt] = k * v;
                p -= k;
                k <<= 1;
            }
            if (p > 0)
            {
                cnt++;
                w2[cnt] = p * w;
                v2[cnt] = p * v;
            }
        }
    }

    for (int i = 1; i <= cnt; i++)      // 有限件的打包件统一当 01 物品，逆序
        for (int j = T; j >= w2[i]; j--)
            f[j] = max(f[j], f[j - w2[i]] + v2[i]);

    cout << f[T] << endl;
    return 0;
}
P2851[USACO2006 Dec] The Fewest Coins SUSACO 2006提高+/省选-
题意
商品价格 TT。你手上第 ii 种硬币有有限枚；店家找零的硬币无限枚。你付出若干、店家找回若干，求这笔交易经手硬币总数最少。
对应关系（两个背包合成）
付款端：自己的硬币有限 → 多重背包，求「凑出金额 j≥Tj\ge T 的最少枚数」fpay[j]fpay[j]（二进制拆分，逆序，min⁡\min 计数）。找零端：店家硬币无限 → 完全背包，求「凑出金额 jj 的最少枚数」fchg[j]fchg[j]（正序，min⁡\min）。答案 min⁡j≥T(fpay[j]+fchg[j−T])\min_{j\ge T}\big(fpay[j]+fchg[j-T]\big)。
为什么选它
混合背包的另一副面孔：不是一个背包里混三类物品，而是多重与完全两个背包各算一半再拼。练的是「识别哪端有限、哪端无限，各上对应背包」的分派眼力。超付上界取 T+max⁡(val)2T+\max(val)^2 是经典结论。
转移 · 复杂度
付款 fpay[j]=min⁡(fpay[j],fpay[j−c val]+c)fpay[j]=\min(fpay[j],fpay[j-c\,val]+c)；找零 fchg[j]=min⁡(fchg[j],fchg[j−val]+1)fchg[j]=\min(fchg[j],fchg[j-val]+1)。时间约 O ⁣((T+max⁡val2)⋅(n+∑log⁡ci))O\!\big((T+\max val^2)\cdot(n+\sum\log c_i)\big)。
参考代码（付款多重 + 找零完全）
C++
在洛谷打开 P2851 
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 1e9;
int val[105], c[105];        // 第 i 种硬币面值、付款端持有数量
int fpay[100005];            // 付款端：凑「≥ 目标」的最少枚数（多重）
int fchg[100005];            // 找零端：凑「恰好」的最少枚数（完全）

int main()
{
    int n, T;                           // 硬币种数、商品价格
    cin >> n >> T;
    int mx = 0;                         // 最大单面值（决定超付上界）
    for (int i = 1; i <= n; i++) { cin >> val[i]; mx = max(mx, val[i]); }
    for (int i = 1; i <= n; i++)   cin >> c[i];

    int LIM = T + mx * mx;              // 付款可枚举到的上界（经典界）
    for (int j = 1; j <= LIM; j++) fpay[j] = fchg[j] = INF;

    // 付款端：硬币有限 → 多重背包，二进制拆分后逆序，求最少枚数
    for (int i = 1; i <= n; i++)
    {
        int rest = c[i], k = 1;
        while (rest > 0)
        {
            int t = min(k, rest);       // 一包 t 枚
            for (int j = LIM; j >= t * val[i]; j--)
                if (fpay[j - t * val[i]] != INF)
                    fpay[j] = min(fpay[j], fpay[j - t * val[i]] + t);
            rest -= t;
            k <<= 1;
        }
    }

    // 找零端：店家硬币无限 → 完全背包，正序，求最少枚数
    for (int i = 1; i <= n; i++)
        for (int j = val[i]; j <= LIM; j++)
            if (fchg[j - val[i]] != INF)
                fchg[j] = min(fchg[j], fchg[j - val[i]] + 1);

    int ans = INF;                      // 枚举「实付 j 元、找零 j−T 元」
    for (int j = T; j <= LIM; j++)
        if (fpay[j] != INF && fchg[j - T] != INF)
            ans = min(ans, fpay[j] + fchg[j - T]);

    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

练习

说明：纯「三类物品同题混装」的洛谷原生题目池很窄，真正综合的题多半把混合骨架藏进更大的模型里。因此这里用各分支的代表题组合覆盖：先用一道纯完全、一道纯有限件，把混合骨架的两条支路分别练熟，再回头做上面的 P1833 就水到渠成。

P1616疯狂的采药混合骨架的『完全』分支：草药可无限次采，先把它当纯完全背包正推练手，f[j]=max(f[j],f[j−w]+v)，j 从 w 到 T 正序。注意 f 与答案可能超 int，开 long long。在洛谷打开
P1077[NOIP2012 普及组] 摆花混合骨架的『有限件（多重）』分支，且是计数版：f[j] 表示前几种花恰好摆 j 盆的方案数，每种不超过 a_i 盆；把 max 换成累加，那一维件数可用前缀和优化掉。在洛谷打开
回 A 部分页的「装包大师」时，试着给每件宝物先贴个标签：这件只有一件、那件成箱、另一件管够，混合背包做的就是这道「逐件分派」的分诊，再把三条支路各自转移。

已进入 混合背包 · 背包 DP · DP大师