背包问题系统讲义：18 个模型族、建模方法、C++ 模板与洛谷题单

理解背包，最有效的方法不是记住几十个名字，而是把一道题拆成三个相互独立的问题：

物品怎么选？状态记录什么？答案怎样合并？

例如，“树形依赖 + 恰好选 $k$ 个 + 统计最优方案数”并不是一种需要重新背诵的算法，而是三个已有模型的组合。

下面参考《背包九讲》原始仓库、OI Wiki、cp-algorithms，以及洛谷上的专题文章和题解，按这个思路整理成 18 个模型族。其中会明确区分：基础背包模型、目标与状态的变形、优化方法，以及借用背包状态结构的综合问题。它们可以组合，因此不存在一个有限、互斥且囊括所有组合的“背包名称清单”。(GitHub)

题单共 102 个分类条目，去重后 86 道题，每个模型族至少 5 题。同一道题可能属于多个模型族，表中会说明它具体训练什么。AT_、CF 编号也均指向洛谷收录的题目页面。

配套文件：

下载 C++17 模板包、示例程序与对拍程序
下载中文分类练习题单
单独查看完整 C++ 模板头文件

模板包中的核心实现已经通过 95,656 项小规模穷举与随机对拍检查。这不等于已经在下面每一道题上提交通过；综合题仍需要根据题意改写状态、边界和输入输出。

---

一、先建立统一的分析框架

1. 背包问题的四条分类轴

分类角度	要问的问题	典型情况
选择次数	每件或每类物品能选多少次？	0-1、完全、多重、混合
选择关系	物品之间是否互相限制？	分组、主附件、依赖树、捆绑
状态与约束	哪些量必须保留，才能决定后续转移？	容量、多维费用、件数、差值、余数、时间
优化目标	同一个状态的不同方案如何合并？	最大值、最小值、可行性、方案数、概率、前 $K$ 优解

二进制拆分、单调队列、bitset、折半搜索、同余最短路，是解决这些模型的工具，不应与“每件物品选几次”混为同一层分类。

2. 统一符号

本文约定：

$$n=\text{物品数或种类数},\qquad C=\text{容量},$$ $$w_i=\text{费用或体积},\qquad v_i=\text{价值},\qquad s_i=\text{数量上限}.$$

“费用”不一定是钱，也可以是时间、重量、人数、机器数等。

除特别说明，完全背包和多重背包模板要求 $w_i>0$。有限的零费用物品可以单独处理；无限的零费用物品则可能造成价值无界或方案数无限。

3. 初始化比循环方向更重要

先决定 f[j] 的精确含义。

状态含义	初始状态
恰好使用 $j$ 费用的最大价值	f[0]=0，其余 -INF
容量不超过 $j$ 的最大价值，允许空集	可以全部初始化为 0
恰好达到 $j$ 的最小费用	f[0]=0，其余 INF
能否恰好达到 $j$	f[0]=true，其余 false
恰好达到 $j$ 的方案数	f[0]=1，其余 0

推荐初学时优先使用“恰好状态”：

$$f[j]=\text{恰好使用 }j\text{ 费用的最优值}.$$

这样，“恰好装满”回答 f[C]，“不超过容量”回答：

$$\max_{0\le j\le C}f[j].$$

本文代码片段默认使用下面的公共定义；完整实现见附件。

cpp
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using i128 = __int128_t;

const ll INF = (1LL << 62);
const ll NEG = -INF;

struct Item {
    int w;
    ll v;
};

vector<ll> init_exact(int C) {
    vector<ll> f(C + 1, NEG);
    f[0] = 0;
    return f;
}

所有有限中间结果都应安全落在 long long 和所用哨兵范围内。不要直接让不可达的 NEG 参与加法。

---

二、18 个背包模型族

1. 0-1 背包：每件物品至多选择一次

识别特征

有若干相互独立的物品，每件只有“选”和“不选”两种决策。

二维定义：

$$f_i[j]=\text{前 }i\text{ 件物品，恰好使用 }j\text{ 费用的最大价值}.$$

按第 $i$ 件是否选择分类：

$$f_i[j]=\max\left(f_{i-1}[j],\ f_{i-1}[j-w_i]+v_i\right).$$

为什么一维压缩必须倒序？

两种转移都来自上一层。

倒序枚举 j 时，较小下标 f[j-w] 尚未被本轮修改，仍然表示上一层状态。

例如只有一件 $(w,v)=(2,3)$ 的物品，容量为 4。正序更新会先得到 f[2]=3，再用它得到 f[4]=6，相当于同一件物品选了两次。

cpp
void zero_one(vector<ll>& f, int w, ll v) {
    int C = (int)f.size() - 1;

    for (int j = C; j >= w; --j) {
        if (f[j - w] == NEG) continue;
        f[j] = max(f[j], f[j - w] + v);
    }
}

时间复杂度 $O(nC)$，空间复杂度 $O(C)$。

常见建模变形

“最多完成多少任务”可以令每件物品价值为 1；“最多装进去多少体积”可以令价值等于体积。

如果每个事件无论成功或失败都有基础收益，可以先统一计入基础收益，再把“升级决策”建成 0-1 物品。例如 P1802 可把失败经验作为基础，花费药物获得的增量是“成功经验减失败经验”。(Luogu)

洛谷练习

题目	训练重点
P1048 采药	标准时间—价值模型。(Luogu)
P1049 装箱问题	价值等于体积，最后求剩余空间。(Luogu)
P1060 开心的金明	正确转换“价格 × 重要度”。(Luogu)
P1802 5 倍经验日	基础收益加可选升级，注意零消耗情况。(Luogu)
P2871 Charm Bracelet	标准 0-1 背包巩固。(Luogu)

---

2. 完全背包：每类物品可以无限选择

状态转移

直接枚举数量：

$$f_i[j] = \max_{k\ge 0,\ kw_i\le j} \left(f_{i-1}[j-kw_i]+kv_i\right).$$

利用同一层已经算出的状态，可以化成：

$$f_i[j] = \max\left(f_{i-1}[j],\ f_i[j-w_i]+v_i\right).$$

这里第二项来自当前层，因此一维压缩要正序更新。(CP Algorithms)

cpp
void complete(vector<ll>& f, int w, ll v) {
    int C = (int)f.size() - 1;

    for (int j = w; j <= C; ++j) {
        if (f[j - w] == NEG) continue;
        f[j] = max(f[j], f[j - w] + v);
    }
}

时间复杂度 $O(nC)$，空间复杂度 $O(C)$。

关键辨析

完全背包不是“物品很多”的同义词，而是数量限制在当前容量范围内不起作用。

若某类物品有 $s_i$ 件，并且：

$$s_iw_i\ge C,$$

那么在这一次容量为 $C$ 的最值或可行性计算中，可以按无限件处理。

但如果问题统计有标号副本的选择方案数，数量与副本身份仍然可能影响答案，不能只按容量判断。

洛谷练习

题目	训练重点
P1616 疯狂的采药	无限件最大价值。(Luogu)
P2722 总分 Score Inflation	时间分配型完全背包。(Luogu)
P1853 投资的最大效益	完全背包嵌入跨年度再投资。(Luogu)
P2918 Buying Hay	至少满足需求的最小费用，不是普通“不超过”。(Luogu)
P1679 神奇的四次方数	无限面值，恰好凑数的最少件数。(Luogu)

---

3. 多重背包：每类物品有数量上限

基本转移

$$f_i[j] = \max_{0\le k\le s_i,\ kw_i\le j} \left(f_{i-1}[j-kw_i]+kv_i\right).$$

直接枚举数量的代价较大，通常使用二进制拆分或单调队列。

3.1 二进制拆分

把数量上限拆成若干包，例如：

$$13=1+2+4+6.$$

每个包作为一件 0-1 物品，费用与价值同时乘以包内件数。

关键不是每个整数都恰好表示一次，而是 $0$ 到 $s_i$ 的每个数量都能表示，且不会表示出超出上限的数量。(Luogu)

cpp
void bounded_binary(vector<ll>& f, int w, ll v, int cnt) {
    int C = (int)f.size() - 1;
    cnt = min(cnt, C / w);

    for (ll k = 1; cnt > 0; k <<= 1) {
        int t = (int)min<ll>(k, cnt);
        zero_one(f, w * t, v * t);
        cnt -= t;
    }
}

复杂度：

$$O\left(C\sum_i\log(s_i+1)\right).$$

重要：二进制拆分通常不能直接用于多重背包方案计数。

例如上限为 6，拆成 $1,2,3$。选择 3 件既可表示为“选 3”，又可表示为“选 1 和 2”，产生重复计数。

它保持的是可达数量与最优值，不一定保持方案数量。

3.2 单调队列优化

固定费用对 $w_i$ 的余数 $r$，写成：

$$j=r+kw_i.$$

令上一层为 old，则：

$$f[r+kw] = kv+ \max_{t\in[\max(0,k-s),\,k]} \left(old[r+tw]-tv\right).$$

括号内是一个滑动窗口最大值，使用单调队列即可。每个状态进出队列至多一次，因此一类物品的复杂度为 $O(C)$。(CP Algorithms)

cpp
void bounded_queue(vector<ll>& f, int w, ll v, int cnt) {
    int C = (int)f.size() - 1;
    cnt = min(cnt, C / w);

    vector<ll> old = f;
    fill(f.begin(), f.end(), NEG);

    for (int r = 0; r < w && r <= C; ++r) {
        deque<pair<int, ll>> q;

        for (int k = 0, j = r; j <= C; ++k, j += w) {
            while (!q.empty() && q.front().first < k - cnt)
                q.pop_front();

            if (old[j] != NEG) {
                ll z = old[j] - 1LL * k * v;

                while (!q.empty() && q.back().second <= z)
                    q.pop_back();

                q.push_back({k, z});
            }

            if (!q.empty())
                f[j] = q.front().second + 1LL * k * v;
        }
    }
}

总复杂度 $O(nC)$，空间复杂度 $O(C)$。

洛谷练习

题目	训练重点
P1776 宝物筛选	二进制拆分与单调队列的直接练习。(Luogu)
P1077 摆花	多重背包计数，不能直接套二进制拆分计数。(Luogu)
P2347 砝码称重	有限数量的可达性。(Luogu)
P1833 樱花	有限件与无限件混合。(Luogu)
P1782 旅行商的背包	多重物品与函数型泛化物品组合。(Luogu)
P3423 BAN-Bank Notes	多重最小件数及方案恢复。(Luogu)

---

4. 混合背包与混合转移

4.1 严格意义的混合背包

同一道题中，有些物品只能选一次，有些无限，有些有限。

它不需要新的状态，只需要根据当前物品的类型选择更新方式。

下面自行约定 cnt=-1 表示无限，cnt>=0 表示有限：

cpp
void mixed(vector<ll>& f, int w, ll v, int cnt) {
    if (cnt == -1)
        complete(f, w, v);
    else
        bounded_binary(f, w, v, cnt);
}

输入约定一定要看题面。 例如 P1833 使用数量 0 表示无限，不是这里的 -1。(Luogu)

4.2 更广义的混合转移

一些题不是简单的“不同物品类型混合”，而是：

$$\text{阶段 DP}+\text{阶段内完全转移}+\text{阶段间 0-1 转移}.$$

典型如“飞扬的小鸟”：一个阶段内可以多次上升，但下降是另一种互斥决策；还涉及高度上限与障碍过滤。不能把所有上升、下降操作摊平，扔进一个普通混合背包。(Luogu)

正确方法是先画清楚：

$$\text{上一阶段} \longrightarrow \text{本阶段的合法决策} \longrightarrow \text{过滤约束后的下一阶段}.$$

洛谷练习

题目	训练重点与性质
P1833 樱花	严格的有限件、无限件混合。(Luogu)
P2851 The Fewest Coins	有限硬币付款与无限硬币找零组合。(Luogu)
P1941 飞扬的小鸟	阶段内重复转移与互斥的一次转移，属于综合模型。(Luogu)
P1782 旅行商的背包	多重背包与泛化物品组合。(Luogu)
P2623 物品选取	有限、无限以及函数型物品。(Luogu)

---

5. 分组背包、泛化物品与资源分配

5.1 分组背包

物品被划分为若干组，每组至多选择一件。

设第 $i$ 组的合法选项为 $(w_{ik},v_{ik})$，则：

$$f_i[j] = \max\left( f_{i-1}[j], \max_k\{f_{i-1}[j-w_{ik}]+v_{ik}\} \right).$$

所有选项必须读取同一个旧数组，否则可能把同组的两个选项都选进去。

cpp
void group(vector<ll>& f,
           const vector<Item>& options,
           bool optional = true) {
    vector<ll> g = optional
        ? f
        : vector<ll>(f.size(), NEG);

    for (auto [w, v] : options) {
        for (int j = w; j < (int)f.size(); ++j) {
            if (f[j - w] == NEG) continue;
            g[j] = max(g[j], f[j - w] + v);
        }
    }

    f.swap(g);
}

optional=true 表示每组至多一个；设为 false，表示每组必须恰好选一个选项。

这里使用新旧数组还有一个好处：零费用选项也安全。P1757 的题面允许非负费用，因此不应依赖“所有费用严格为正”才能成立的原地写法。(luogu.com.cn)

5.2 泛化物品：把一整个子问题压成收益函数

设一个“物品”分配 $x$ 单位资源后，能得到的最优收益为：

$$h[x].$$

它不再是单个 $(w,v)$，而是一整条费用—收益曲线。把每个 $(x,h[x])$ 看作同组的一个选项即可：

$$g[j]=\max_{0\le x\le j}\{f[j-x]+h[x]\}.$$

这就是最大加卷积。资源分配、主附件组合、子树合并，都可以从这个角度理解。(GitHub)

例如“给每家公司分配机器”，每家公司是一个组，给它 $0,1,2,\ldots$ 台机器是组内选项。

不能把同一个函数的不同资源用量当成相互独立的 0-1 物品。 否则会重复使用同一个对象。

洛谷练习

题目	训练重点
P1757 通天之分组背包	标准分组，注意零费用。(luogu.com.cn)
P2066 机器分配	资源分配，另有方案与字典序要求。(Luogu)
P5322 排兵布阵	每个城堡的派兵数量形成一组策略。(Luogu)
P1336 最佳课题选择	每个课题的论文数量与耗时函数。(Luogu)
P1782 旅行商的背包	二次收益函数与普通物品的组合。(Luogu)

---

6. 多维费用、选取件数与多个实体背包

6.1 多维费用

每件物品同时消耗多种资源。

例如两维费用 $(a_i,b_i)$，状态：

$$f[x][y]=\text{恰好消耗 }x,y\text{ 两种资源的最大价值}.$$

0-1 转移：

$$f[x][y] = \max\left(f[x][y],f[x-a_i][y-b_i]+v_i\right).$$

cpp
void zero_one_2d(vector<vector<ll>>& f,
                 int a, int b, ll v) {
    int A = (int)f.size() - 1;
    int B = (int)f[0].size() - 1;

    for (int x = A; x >= a; --x) {
        for (int y = B; y >= b; --y) {
            if (f[x - a][y - b] == NEG) continue;
            f[x][y] = max(f[x][y],
                          f[x - a][y - b] + v);
        }
    }
}

初始化仍然只有 f[0][0]=0，其余为 NEG。

复杂度 $O(nAB)$。一般 $d$ 维费用的状态规模为：

$$O\left(\prod_{k=1}^d C_k\right).$$

6.2 “恰好选 $k$ 件”也是一种费用

增加一维：

$$f[j][k]=\text{费用为 }j\text{，恰好选 }k\text{ 件的最优值}.$$

每选一件物品，第二维消耗 1。

类似地，“最多选 $k$ 件”“恰好选 $k$ 种”“至少完成 $k$ 项”，都先考虑是否要记录数量。

6.3 多个实体背包不等于一个大背包

两个容量分别为 $A,B$ 的实体背包，一件物品只能放入其中一个，可以建成：

$$f[x][y]$$

并为每件物品设置“不选、放入第一个、放入第二个”三种互斥选择。

不能直接把容量相加。例如容量为 $4,4$，物品重量为 $3,3,2$，总重量虽为 8，却无法全部装入两个背包。

洛谷练习

题目	训练重点
P1507 NASA 的食物计划	两种资源限制。(Luogu)
P1855 榨取 kkksc03	金钱、时间双约束，最大化数量。(Luogu)
P1910 L 国的战斗之间谍	两种费用的价值最大化。(Luogu)
P1759 通天之潜水	二维背包与字典序方案。(Luogu)
P2732 商店购物 Shopping Offers	多种商品需求量作为多个维度。(Luogu)
P1509 找啊找啊找朋友	双约束，先最大化完成数量，再最小化时间。(Luogu)

---

7. 更换状态轴与覆盖型背包

这一族的共同点是：题面给出的“容量”不一定适合直接作为数组下标。

7.1 反向背包：以价值为下标，最小化重量

当 $C$ 很大，但总价值：

$$S=\sum_i v_i$$

较小时，定义：

$$f[x]=\text{获得恰好 }x\text{ 价值所需的最小重量}.$$

转移：

$$f[x]=\min(f[x],f[x-v_i]+w_i).$$

最后找最大的 $x$，使得 $f[x]\le C$。

cpp
ll value_dimension(const vector<pair<ll, int>>& a, ll C) {
    int S = 0;
    for (auto [w, v] : a) S += v;

    vector<ll> f(S + 1, INF);
    f[0] = 0;

    for (auto [w, v] : a) {
        for (int x = S; x >= v; --x) {
            if (f[x - v] == INF) continue;
            f[x] = min(f[x], f[x - v] + w);
        }
    }

    for (int x = S; x >= 0; --x)
        if (f[x] <= C) return x;

    return 0;
}

复杂度 $O(nS)$，要求价值为非负整数且 $S$ 足够小。

AT_dp_e 和 P14920 都直接体现了“容量巨大、价值总量相对较小”的状态轴选择。(Luogu)

7.2 覆盖型背包：至少满足需求

题目可能要求：

$$\sum w_i\ge H,\qquad \min\sum c_i.$$

此时目标不是“不超过容量”，而是“至少达到需求”。

如果超过 $H$ 的部分对未来没有影响，可以把所有达到或超过 $H$ 的状态压缩为 $H$：

$$j'=\min(H,j+w_i).$$

cpp
ll cover01(const vector<Item>& a, int H) {
    vector<ll> f(H + 1, INF);
    f[0] = 0;

    for (auto [w, cost] : a) {
        auto g = f;

        for (int j = 0; j <= H; ++j) {
            if (f[j] == INF) continue;
            int nj = min<ll>(H, 1LL * j + w);
            g[nj] = min(g[nj], f[j] + cost);
        }

        f.swap(g);
    }

    return f[H];
}

这里新旧数组很重要：截断到 $H$ 后，简单机械地“倒序”未必仍然清晰地表达 0-1 语义。

无限件覆盖还可以直接按剩余需求定义：

$$f[h]=\min_i\left(c_i+f[\max(0,h-w_i)]\right),$$

其中 $w_i>0,c_i\ge0$，从小到大计算 $h$。

7.3 费用接近：拆成“大基数 + 小偏移”

若所有费用满足：

$$w_i=b+\delta_i,\qquad 0\le\delta_i\le D,$$

则选择 $k$ 件、偏移和为 $d$ 的实际费用为：

$$kb+d.$$

可以定义：

$$f[k][d]=\text{对应的最大价值},$$

避免把很大的 $b$ 放进数组。P3985 中所有价格相差不超过 3，正适合这种状态压缩。(Luogu)

洛谷练习

题目	训练重点
AT_dp_e Knapsack 2	价值维度上的最小重量。(Luogu)
P14920 道具商店	金币上限巨大，总攻击力较小。(Luogu)
P1510 精卫填海	至少填够体积的最小消耗。(Luogu)
P2918 Buying Hay	无限物品覆盖需求。(Luogu)
P3423 BAN-Bank Notes	恰好满足金额，最小化有限纸币数量。(Luogu)
P3985 不开心的金明	件数加小偏移量，绕开巨大价格。(Luogu)

---

8. 可行性背包、子集和与划分

8.1 把“最优值”换成真假

$$f[j]=\text{是否能够恰好组成 }j.$$

0-1 转移：

$$f[j]\leftarrow f[j]\lor f[j-w].$$

当只有一维非负整数和时，可以用 bitset 并行处理：

cpp
const int MAXC = 200005; // 按题目上界设置
bitset<MAXC> f;

f[0] = 1;
for (int w : weights)
    f |= f << w;

f << w 对应“在原有可达和上再加一个 $w$”。右侧移位表达式先由旧值计算，因此单次操作表达的是 0-1 选择。

复杂度可视为 $O(nC/\omega)$ 次机器字操作，$\omega$ 通常对应机器字位数。

bitset 不是普通最大价值背包的通用替代品。 它特别适合只有可达与不可达两种状态的情形。

8.2 等和划分与最小差值

总和为 $S$，把物品分成两组，相当于找一个尽量接近 $S/2$ 的可达子集和 $x$。

差值是：

$$|S-2x|.$$

两个相同处理器分配任务时，完成时间是：

$$\max(x,S-x).$$

8.3 多重可行性的“剩余件数”写法

对当前类型 $(w,s)$，令 rem[j] 表示组成 $j$ 后当前类型还剩多少件可用。

cpp
vector<int> rem(C + 1, -1);
rem[0] = 0;

for (auto [w, cnt] : types) {
    for (int j = 0; j <= C; ++j) {
        if (rem[j] >= 0)
            rem[j] = cnt;
        else if (j >= w && rem[j - w] > 0)
            rem[j] = rem[j - w] - 1;
        else
            rem[j] = -1;
    }
}

每类物品 $O(C)$，最后 rem[j]>=0 表示可达。这里存的是辅助信息，不是普通意义上的方案数或价值。

洛谷练习

题目	训练重点
P1049 装箱问题	子集和视角。(Luogu)
P1441 砝码称重	枚举删除集合，再进行可达性计算。(Luogu)
P2347 砝码称重	多重可达性。(Luogu)
P1537 弹珠	多重集合能否等和划分。(Luogu)
P2392 kkksc03 考前临时抱佛脚	每科任务的双处理器划分。(Luogu)
P5020 货币系统	完全背包可达性与冗余面值去除。(Luogu)

---

9. 方案计数背包与生成函数

这一类最重要的问题不是“把 max 改成加法”，而是：

你的转移是否把每个合法方案恰好计算一次？

9.1 0-1 计数

不同物品视为不同对象：

$$f_i[j]=f_{i-1}[j]+f_{i-1}[j-w_i].$$

cpp
vector<int> f(C + 1);
f[0] = 1;

for (int w : weights) {
    for (int j = C; j >= w; --j)
        f[j] = (f[j] + 1LL * f[j - w]) % MOD;
}

相同费用的两件不同物品，通常仍是两种不同选择。

9.2 无限物品：组合与排列的区别

不考虑选择顺序，每种物品处理一次：

cpp
for (int w : weights)
    for (int j = w; j <= C; ++j)
        f[j] = (f[j] + 1LL * f[j - w]) % MOD;

考虑顺序、每种元素可无限使用，按序列的最后一个元素分类：

cpp
for (int j = 1; j <= C; ++j)
    for (int w : weights)
        if (j >= w)
            f[j] = (f[j] + 1LL * f[j - w]) % MOD;

例如面值 1、2，目标 3：

无序组合是 $1+1+1$、$1+2$，共 2 种；有序序列还要区分 $1+2$ 与 $2+1$，共 3 种。

上述有序写法不能拿来统计“每件只能用一次的排列”，因为它没有记录哪些物品已经用过。

9.3 多重计数：滑动窗口求和

同类副本不可区分时：

$$g[j]=\sum_{k=0}^{s}f[j-kw].$$

按模 $w$ 分组，用滑动窗口求和：

cpp
vector<int> g(C + 1);

for (int r = 0; r < w && r <= C; ++r) {
    ll sum = 0;

    for (int j = r; j <= C; j += w) {
        sum += f[j];

        ll out = j - 1LL * (cnt + 1) * w;
        if (out >= 0) sum -= f[out];

        sum = (sum % MOD + MOD) % MOD;
        g[j] = sum;
    }
}

f.swap(g);

若副本有标号，选择 $k$ 件应带上组合数系数：

$$\binom{s}{k},$$

那是另一种计数口径。

9.4 少量类型、多次上限查询：容斥

P1450 只有四种面值，但每次查询的数量上限不同。先预处理无限件方案数 $F[x]$，对每次查询使用：

$$\text{ans} = \sum_{S\subseteq\{1,2,3,4\}} (-1)^{|S|} F\left( T-\sum_{i\in S}(s_i+1)w_i \right).$$

负下标视为 0。每次查询只需枚举 $2^4$ 个集合。(Luogu)

9.5 生成函数视角

把 f[j] 看作多项式的 $x^j$ 系数：

选择限制	对应因子
0-1 物品	$1+x^w$
无限物品	$(1-x^w)^{-1}$
至多 $s$ 件	$1+x^w+\cdots+x^{sw}$
一组选项	各合法选项对应单项式之和

背包计数就是把这些因子相乘。

P4389 的规模使朴素完全背包不够，需要进一步利用：

$$F(x)=\prod_i(1-x^{w_i})^{-1},$$ $$\log F(x)=\sum_i\sum_{k\ge1}\frac{x^{kw_i}}k,$$

再通过形式幂级数指数求 $F$。这是计数背包与多项式算法的结合，不是给普通最大值背包套一个 NTT。(Luogu)

洛谷练习

题目	训练重点
P1164 小 A 点菜	0-1 恰好凑数计数。(Luogu)
P1474 Money System	无限硬币无序组合。(Luogu)
P1077 摆花	多重数量方案计数。(Luogu)
P1832 A+B Problem（再升级）	以质数作为无限面值。(Luogu)
P1025 数的划分	恰好分成 $k$ 个无序正整数。(Luogu)
P1450 硬币购物	无限预处理加有限上限容斥。(Luogu)
P4389 付公主的背包	生成函数、形式对数与指数，进阶题。(Luogu)

---

10. 负权、差值、模数与代数约束背包

这类题的共同点是：把原来的限制转换成可累加的状态量。

10.1 有符号费用

若状态增量可能为负，容量不再天然单调。

设：

$$S=\sum_i |d_i|,$$

把状态范围 $[-S,S]$ 平移成数组下标 $[0,2S]$。

cpp
vector<ll> f(2 * S + 1, NEG);
f[S] = 0;

for (auto [delta, value] : items) {
    auto g = f;

    for (int j = 0; j <= 2 * S; ++j) {
        int nj = j + delta;
        if (f[j] == NEG || nj < 0 || nj > 2 * S)
            continue;

        g[nj] = max(g[nj], f[j] + value);
    }

    f.swap(g);
}

正负增量同时存在时，使用旧数组最稳妥。不要凭“0-1 必须倒序”直接处理负下标转移。

10.2 两组相等：记录差值而不是两个总和

要求两组和相等：

$$\sum A-\sum B=0.$$

每件物品有“放左边、放右边、不选”三个选项，对差值的增量分别为：

$$+w_i,\quad -w_i,\quad 0.$$

对于两座等高塔，还可以令：

$$f[d]=\text{两塔高度差为 }d\text{ 时，较矮塔的最大高度}.$$

加入长度 $x$：

$$g[d+x]\gets\max(g[d+x],f[d]),$$ $$g[|d-x|]\gets\max(g[|d-x|],f[d]+\min(d,x)).$$

加上不选的转移，即得到一个更紧凑的差值状态设计。

10.3 余数背包

要求总和满足某种模数限制：

$$f[r]=\text{总和模 }m\text{ 为 }r\text{ 的方案信息}.$$

0-1 计数示例：

cpp
vector<int> f(m);
f[0] = 1;

for (ll x : a) {
    int t = (x % m + m) % m;
    auto g = f;

    for (int r = 0; r < m; ++r) {
        int nr = (r + t) % m;
        g[nr] = (g[nr] + 1LL * f[r]) % MOD;
    }

    f.swap(g);
}

余数之间存在环，不能通过简单正序或倒序避免重复选择，应该保留层次。

若题目要求非空集合，而空集满足目标余数，最后要减去空集。

10.4 比例约束与分数规划

等式：

$$\frac{\sum a_i}{\sum b_i}=k$$

可以转换为：

$$\sum(a_i-kb_i)=0.$$

最大化比例：

$$\max\frac{\sum v_i}{\sum w_i},$$

可以二分答案 $R$，检查是否存在合法非空集合满足：

$$\sum(v_i-Rw_i)\ge0.$$

这时背包中的“价值”改成 $v_i-Rw_i$，原有费用、依赖、件数限制保留。

例如 P4377 使用“总重量至少达到 $W$”的判定；P4322 则保留“依赖关系 + 恰好选择 $K$ 人”。(Luogu)

对于 P4377 要求输出比例乘 1000 后向下取整的形式，也可以二分整数 $X$，使用：

$$1000v_i-Xw_i$$

作为判定价值，从而避免最终浮点下取整的边界问题。

洛谷练习

题目	训练重点
P2340 Cow Exhibition	有符号属性和作为状态。(Luogu)
P2946 Cow Frisbee Team	非空子集的模数计数。(Luogu)
P1282 多米诺骨牌	正负差值，次级目标为最少翻转。(Luogu)
P1651 塔	两组等和，差值与较矮高度。(Luogu)
P1877 音量调节	每阶段必须加或减，并限制中间状态。(Luogu)
CF366C Dima and Salad	比例等式转成零差值。(Luogu)
P4377 Talent Show	分数规划加覆盖型背包。(Luogu)
P4322 最佳团体	分数规划加依赖与选取件数。(Luogu)

---

11. 依赖背包、捆绑选择与缩点

11.1 主件与附件

“选择附件必须先选择主件”。

如果一个主件只有两个附件，那么合法购买组合是：

$$\{\text{主件}\},\ \{\text{主件、附件1}\},\ \{\text{主件、附件2}\},\ \{\text{主件、附件1、附件2}\}.$$

把这些组合放进一个组，再额外允许“整组不选”，即可转成分组背包。P1064 就是经典的这个模型。(Luogu)

附件很多时，不能枚举 $2^k$ 个组合，应先求“选了主件之后，附件可形成怎样的费用—收益函数”。

11.2 一般父依赖

如果每个物品至多依赖一个父物品，依赖关系形成森林：

$$\text{选子节点}\Longrightarrow\text{选父节点}.$$

通常可以树形背包。但对于只有父依赖、节点费用和收益可加的情形，还可以做到 $O(nC)$，不必对子树做 $C^2$ 卷积。相关泛化物品文章也讨论了这类更高效的依赖背包处理。(Luogu)

一种直观实现是“先序遍历 + 跳过子树”。

设 ord[i] 是先序序列第 $i$ 个节点，out[u] 是节点 $u$ 的整棵子树结束后的序列位置。

处理 $u$ 时：

$$\text{不选 }u\Rightarrow\text{整棵子树都不能选，跳到 }out[u];$$ $$\text{选 }u\Rightarrow\text{支付费用，继续处理 }i+1.$$

下面的 dp[i][j] 使用“剩余预算为 $j$”的含义：

cpp
vector<vector<ll>> dp(n + 1, vector<ll>(C + 1, 0));

for (int i = n - 1; i >= 0; --i) {
    int u = ord[i];

    for (int j = 0; j <= C; ++j) {
        dp[i][j] = dp[out[u]][j];

        if (j >= w[u]) {
            dp[i][j] = max(
                dp[i][j],
                dp[i + 1][j - w[u]] + v[u]
            );
        }
    }
}

答案为 dp[0][C]。完整的遍历、恰好装满版本在附件的 dependency_preorder 中。

这个方法依赖“拒绝一个节点，就拒绝整段子树”的结构，不适用于带任意跨子树相互作用的树形 DP。

11.3 必须一起选：并查集合并

若关系是：

$$\text{选 }u\Longleftrightarrow\text{选 }v,$$

连通块中的物品必须一起选择。用并查集合并，费用与价值求和，每个连通块再作为一件 0-1 物品。P1455 是这种双向捆绑关系。(Luogu)

11.4 依赖中有环：强连通分量缩点

依赖环中只要选一个节点，就必须选完整个环，所以一个强连通分量可以整体缩成一件物品。

但要特别注意：

缩点后是 DAG，不代表自动变成森林。

P2515 的“每个软件至多依赖一个软件”提供了进一步转成森林的条件。一般多前驱依赖 DAG 不能直接照搬树形背包。(Luogu)

洛谷练习

题目	训练重点
P1064 金明的预算方案	主件、附件与分组转换。(Luogu)
P2014 选课	先修课森林，恰好选定数量。(Luogu)
P2967 Video Game Troubles	购买主机后才能选择相应游戏。(Luogu)
P2515 软件安装	依赖环缩点，再处理森林。(Luogu)
P1455 搭配购买	并查集捆绑，再做 0-1 背包。(Luogu)
P1273 有线电视网	叶子收益与路径激活费用，属于更一般的依赖树变式。(Luogu)

---

12. 树形背包与子树卷积

与上一类的区别

依赖背包强调“谁能选”；树形背包强调“如何合并不同子树的资源与信息”。

一般定义：

$$f_u[k]=\text{节点 }u\text{ 的子树中，使用 }k\text{ 单位资源的最优值}.$$

合并儿子 $v$：

$$g[i+j]=\max\left(g[i+j],f_u[i]+f_v[j]\right).$$

如果存在边费用、覆盖状态、颜色关系等，还要在转移中加入对应贡献或状态条件。

通用最大加卷积

cpp
vector<ll> merge_max(const vector<ll>& a,
                     const vector<ll>& b,
                     int C) {
    int len = min(C + 1, (int)a.size() + (int)b.size() - 1);
    vector<ll> g(len, NEG);

    for (int i = 0; i < (int)a.size() && i < len; ++i) {
        if (a[i] == NEG) continue;

        for (int j = 0; j < (int)b.size() && i + j < len; ++j) {
            if (b[j] == NEG) continue;
            g[i + j] = max(g[i + j], a[i] + b[j]);
        }
    }

    return g;
}

对于“选子必须选父”的版本，可令每棵返回的子树状态强制选择根：

$$f_u[w_u]=v_u.$$

合并某个儿子之前，再给该儿子的状态加入“整棵子树不选”的选项：

$$f_v[0]\gets\max(f_v[0],0).$$

森林可以连接一个费用、价值均为 0 的虚拟根。

常见附加状态

覆盖问题可能需要：

$$f_u[k][\text{是否放装置}][\text{是否已被覆盖}].$$

颜色问题可能记录子树黑点数量；路径贡献问题则把每条边对跨越这条边的点对数量单独计算。

例如一条边把树分成大小为 $s,n-s$ 的两部分，其中一侧有 $b$ 个黑点，全树有 $K$ 个黑点，那么这条边参与的同色点对数量可以写为：

$$b(K-b)+(s-b)\bigl((n-K)-(s-b)\bigr).$$

这就把“点对距离和”转成了边贡献与背包计数状态。

复杂度不能只看三重循环

一般费用维度的朴素子树卷积，可给出 $O(nC^2)$ 上界。

但当背包维度是“选取节点数量”，并把循环范围限制在实际子树大小和 $K$ 以内时，标准合并的总复杂度可以是 $O(nK)$，而不是机械地写成 $O(nK^2)$。这个结论有特定的状态规模与合并条件，不能套到所有树形背包。(Luogu)

洛谷练习

题目	训练重点
P2014 选课	按选取数量合并子树。(Luogu)
P2015 二叉苹果树	保留与根连通的若干条边。(Luogu)
P1273 有线电视网	叶子用户数、收益和启用边费用。(Luogu)
P3177 树上染色	黑点数量背包与同色点对距离贡献。(Luogu)
P4516 潜入行动	数量背包加覆盖状态，注意装置不覆盖自身。(Luogu)

---

13. 顺序、时间与多阶段背包

13.1 先证明顺序，再做背包

有些物品的价值依赖完成时间。例如任务 $i$ 耗时 $t_i$，在时刻 $T$ 完成的收益为：

$$a_i-b_iT.$$

这时物品不是无序集合。要先证明一个最优顺序。

比较相邻任务 $i,j$，交换论证得到：

$$i\text{ 在 }j\text{ 前面更优} \Longleftrightarrow t_i b_j\le t_j b_i.$$

因此按这个交叉乘积关系排序，再进行 0-1 背包。

cpp
struct Job {
    ll a, b;
    int t;
};

sort(jobs.begin(), jobs.end(), [](const Job& x, const Job& y) {
    return (i128)x.t * y.b < (i128)y.t * x.b;
});

auto f = init_exact(C);

for (auto x : jobs) {
    for (int j = C; j >= x.t; --j) {
        if (f[j - x.t] == NEG) continue;
        f[j] = max(f[j],
                   f[j - x.t] + x.a - 1LL * x.b * j);
    }
}

这里 j 是当前任务完成的时刻，不是它开始的时刻。P1417 是这一模型的直接训练。(Luogu)

截止时间问题则常需要先按截止时间排序，并限制转移后的完成时间。是否允许等于截止时间必须看题面；CF864E 要在物品开始燃烧之前完成救出。(Luogu)

13.2 分阶段再投资

若允许无手续费、整数件、无限量买卖，并且每天价格已知，则一次“今天买入，明天卖出”可建成完全背包：

$$w_i=p_{d,i},\qquad v_i=p_{d+1,i}-p_{d,i}.$$

cpp
for (int d = 0; d + 1 < days; ++d) {
    vector<ll> f(cash + 1, 0);

    for (int i = 0; i < kinds; ++i) {
        complete(f, price[d][i],
                 price[d + 1][i] - price[d][i]);
    }

    cash += f[cash];
}

这要求资金规模适合做数组下标，也要求没有手续费、交易次数、持仓上限等额外条件。

13.3 阶段合法性不能只在终点检查

垃圾陷阱、音量调节、小鸟穿管道等题，经常要求中间每个阶段都合法。

因此要区分：

$$\text{只要求最终满足} \quad\text{与}\quad \text{每一步都必须满足}.$$

状态转移顺序和过滤时机是模型的一部分。

洛谷练习

题目	训练重点
P1417 烹调方案	交换论证排序，收益依赖完成时间。(Luogu)
P1156 垃圾陷阱	按时间处理生存、食用与堆高。(Luogu)
P1853 投资的最大效益	年度再投资。(Luogu)
P5662 纪念品	逐日完全背包交易。(Luogu)
P2938 Stock Market	逐日资金转移与投资。(Luogu)
CF864E Fire	截止时间排序、时间背包与方案恢复。(Luogu)

---

14. 概率权重与非加法收益

这一族不是一种新的物品次数限制，而是改变了“状态里存什么，以及怎样合并”。

其中有些题属于严格背包，有些属于借用背包状态结构的概率 DP，应当区分。

14.1 概率背包：累加互斥事件概率

若第 $i$ 个独立事件以概率 $p_i$ 成功，成功使状态增加 $w_i$，则：

$$g[j]\mathrel{+}=f[j](1-p_i),$$ $$g[j+w_i]\mathrel{+}=f[j]p_i.$$

cpp
vector<long double> f(S + 1);
f[0] = 1;

for (auto [w, p] : events) {
    vector<long double> g(S + 1);

    for (int j = 0; j <= S; ++j) {
        g[j] += f[j] * (1 - p);

        if (j + w <= S)
            g[j + w] += f[j] * p;
    }

    f.swap(g);
}

这里是在统计随机结果，不是在从成功与失败中选择更好的那个，因此不能用 max。

一个实用检查是：没有丢弃状态时，概率分布之和应接近 1。

若题目存在可控决策，就可能出现“每个决策内部求期望，决策之间再取最大值”的结构，需要额外论证，不能与上面的独立随机转移混同。

14.2 通过计数求概率与期望

随机排列中，前 $k$ 个对象的集合在所有大小为 $k$ 的子集中等概率出现。

因此可以用：

$$\Pr(\text{前 }k\text{ 个满足容量}) = \frac{\text{大小为 }k\text{ 且总费用合法的子集数}} {\binom nk}.$$

再利用：

$$E[X]=\sum_{k\ge1}\Pr(X\ge k)$$

求期望。CF261B 可以从这个角度把随机排列问题连接到二维计数背包。(Luogu)

14.3 最大乘积收益

收益可能不是相加，而是相乘。

例如每组选择一个方案，方案费用为 $c$，收益因子为 $k$：

$$g[j+c]=\max(g[j+c],f[j]\cdot k).$$

当只关心乘积是否至少达到 $M$，且后续乘数均不小于 1，可以将乘积截断到 $M$，防止溢出：

cpp
ll nv = (ll)min<i128>(M, (i128)f[j] * k);
g[j + cost] = max(g[j + cost], nv);

初始乘积为 1，不可达状态可以使用 0。P5365 中不购买某个英雄的皮肤相当于该组乘数为 1，购买 $k$ 款则贡献乘数 $k$。(Luogu)

洛谷练习

题目	训练重点与性质
AT_dp_i Coins	独立事件成功次数分布。(Luogu)
P10504 守卫者的挑战	成功次数与容量差的联合概率；中间负容量差不一定应被丢弃。(Luogu)
CF261B Maxim and Restaurant	子集计数转随机前缀概率与期望。(Luogu)
CF518D Ilya and Escalator	有上限的随机计数，属于状态结构扩展。(Luogu)
P5365 英雄联盟	分组选择，预算下最大乘积，再找最小达标费用。(Luogu)

---

15. 最优方案恢复、最优方案数、字典序与前 $K$ 优解

这些目标通常附着在前面的基础结构上，并不是新的物品类型。《背包九讲》也将它们放在背包问法的变化中讨论。(GitHub)

15.1 恢复一个最优方案

最稳妥的方法是保留阶段维度：

$$F[i][j]=\text{前 }i\text{ 件物品对应的最优值}.$$

倒推时判断本件是否被选择：

cpp
vector<int> chosen;
int j = target;

for (int i = n; i >= 1; --i) {
    if (F[i][j] == F[i - 1][j]) continue;

    chosen.push_back(i);
    j -= w[i];
}

reverse(chosen.begin(), chosen.end());

平局时跳过当前物品，可以恢复某个最优方案，但不保证题目要求的字典序。

不要轻易给一维 DP 存一个会不断被覆盖的 pre[j]。 后续更新可能改变前驱状态的历史含义，导致恢复出重复使用同一件物品的路径。可靠做法是保留阶段、保存持久化决策节点，或使用经过证明的分治恢复。

15.2 统计最优方案数

每个状态保存：

$$(\text{最优值},\text{达到该最优值的方案数}).$$

候选更优时覆盖；候选相等时累加：

cpp
void relax(ll& best, int& ways,
           ll value, int cnt, int MOD) {
    if (value > best) {
        best = value;
        ways = cnt;
    } else if (value == best) {
        ways = (ways + 1LL * cnt) % MOD;
    }
}

初始化应是：

$$best[0]=0,\quad ways[0]=1;$$

其余状态不可达、方案数为 0。

若计算的是“总费用不超过 $C$”的最优方案总数，使用恰好费用状态后，应把所有达到全局最优值的费用状态的方案数相加。

15.3 字典序：先明确比较对象

以下规则完全不同：

“输出所选编号序列字典序最小”；“每家公司分配数量构成的向量字典序最小”；“先最少件数，再编号最小”。

通常可以计算后缀最优值，然后从前往后尝试是否还能完成全局最优解。但相等时选还是不选，取决于题目比较的对象，不能套一个万能平局规则。

15.4 前 $K$ 优解

把每个状态的单个最优值，扩展成降序排列的前 $K$ 个值。

对于 0-1 背包：

$$L_i[j] = \operatorname{TopK}\left( L_{i-1}[j]\cup \{x+v_i:x\in L_{i-1}[j-w_i]\} \right).$$

两个输入序列都已经有序，可以 $O(K)$ 合并：

cpp
auto old = f; // f[j] 是降序 vector<ll>

for (int j = w; j <= C; ++j) {
    auto take = old[j - w];
    for (ll& x : take) x += v;

    vector<ll> g;
    merge(old[j].begin(), old[j].end(),
          take.begin(), take.end(),
          back_inserter(g), greater<ll>());

    if ((int)g.size() > K) g.resize(K);
    f[j] = move(g);
}

复杂度 $O(nCK)$。

必须区分“前 $K$ 个不同方案”和“前 $K$ 个不同价值”。P1858 要求物品集合不同，价值相同的两个集合仍占两个名次，不能去重。它虽然叫“多人背包”，却不是把一批互斥物品分配到多个实体背包。(Luogu)

洛谷练习

题目	训练重点
P2066 机器分配	分配方案与题目指定的字典序规则。(Luogu)
P1759 通天之潜水	二维最优方案及编号序列字典序。(Luogu)
P3423 BAN-Bank Notes	恢复每种纸币的使用数量。(Luogu)
P1858 多人背包	恰好装满的前 $K$ 个不同方案。(Luogu)
P1509 找啊找啊找朋友	主目标最大数量，次目标最少时间。(Luogu)
CF864E Fire	恢复满足截止时间的有序选择方案。(Luogu)

---

16. 大数值、小规模：折半背包与折半搜索

什么时候不该开容量数组？

当：

$$n\approx 40,\qquad C\text{ 很大},$$

容量 DP 不合适，完整枚举 $2^n$ 又太慢。

将物品分成两半，分别枚举：

$$2^{n/2}$$

个子集，再通过排序和二分合并。

严格说，这是一种背包问题的精确搜索方法，不是普通容量 DP 的循环优化。

16.1 统计不超过容量的子集数

分别得到左右两半的子集和 $A,B$。

对于每个 $x\in A$，统计：

$$\#\{y\in B:y\le C-x\}.$$

cpp
vector<ll> subset_sums(const vector<ll>& a, ll C) {
    vector<ll> s{0};

    for (ll w : a) {
        int len = s.size();

        for (int i = 0; i < len; ++i) {
            if (w <= C && s[i] <= C - w)
                s.push_back(s[i] + w);
        }
    }

    return s;
}

ll mitm_count(const vector<ll>& a, ll C) {
    int m = a.size() / 2;

    auto L = subset_sums(vector<ll>(a.begin(), a.begin() + m), C);
    auto R = subset_sums(vector<ll>(a.begin() + m, a.end()), C);

    sort(R.begin(), R.end());

    ll ans = 0;
    for (ll x : L)
        ans += upper_bound(R.begin(), R.end(), C - x) - R.begin();

    return ans;
}

上面的剪枝要求费用非负。

计数时不能随便对相同子集和去重。 两个不同子集可能具有相同的和，它们仍然是不同方案。

16.2 最大价值版本

枚举每半的：

$$(\text{费用},\text{价值}).$$

右半按费用排序，维护前缀最大价值。对左半每个状态，二分找到费用不超过 $C-w$ 的最大位置，配上右半前缀最优值。

其复杂度为：

$$O\left(n2^{n/2}\right)$$

量级，空间 $O(2^{n/2})$。

16.3 不止两种决策

两边分组问题中，每件物品可能有“放左、放右、不选”三种状态，折半后的规模变成 $3^{n/2}$。

如果题目统计的是“能够平衡的选中集合”，而不是“平衡分配方法”，还需要按照选中集合去重，不能直接把左右分配次数当答案。

洛谷练习

题目	训练重点
P4799 世界冰球锦标赛	统计预算内的子集数量。(Luogu)
AT_abc184_f Programming Contest	最大可行子集和。(Luogu)
CF888E Maximum Subsequence	子集和取模后的最优化。(Luogu)
P3067 Balanced Cow Subsets	三种分配状态，区分集合与分配方法。(Luogu)
P5194 Scales	先利用砝码快速增长条件限制有效规模，再考虑搜索；不能只看到名义 $n\le1000$ 就直接折半。(Luogu)

---

17. 动态增删、缺一与区间生效背包

这是“背包不只算一次”的模型族。

17.1 计数背包可以代数删除

对于一个重量为 $w$ 的 0-1 物品，加入前后满足：

$$F(x)=G(x)(1+x^w).$$

比较系数：

$$F[j]=G[j]+G[j-w],$$

所以：

$$G[j]=F[j]-G[j-w].$$

因为右边需要已经恢复出来的 $G[j-w]$，删除时应正序：

cpp
void add_item(vector<int>& f, int w, int MOD) {
    for (int j = (int)f.size() - 1; j >= w; --j)
        f[j] = (f[j] + 1LL * f[j - w]) % MOD;
}

void erase_item(vector<int>& f, int w, int MOD) {
    for (int j = w; j < (int)f.size(); ++j)
        f[j] = (f[j] - 1LL * f[j - w] + MOD) % MOD;
}

要求 $w>0$，并且要删除的副本确实存在。

这里不需要模数为质数，因为不是对任意数求模逆，而是利用常数项为 1 的因子逐项恢复。

最大值背包通常不能这样删除。 max 丢弃了次优信息，删除一个物品后，之前丢弃的信息可能重新成为最优。

17.2 每次独立删一个：缺一分治

要求分别回答“删掉第 $i$ 件后的答案”。

递归维护区间 $[l,r)$，并保证当前 DP 已加入区间外的所有物品：

递归左半之前，加入右半全部物品；递归右半之前，恢复原状态，再加入左半全部物品。

到叶子 $i$ 时，DP 恰好包含除 $i$ 外的所有物品。

若单件更新 $O(C)$，总时间为：

$$O(nC\log n).$$

这种方法也可把“删除一件”换成“删除一整类有限物品”，只要加入一类时使用正确的多重背包更新。(Luogu)

17.3 一段时间内有效：时间线段树

若物品从插入时刻 $l$ 到删除时刻 $r$ 有效，它的生命区间是：

$$[l,r).$$

把物品加入覆盖这个时间区间的线段树节点。DFS 线段树时：

进入节点，加入该节点的物品；到叶子，回答此刻询问；离开节点，恢复之前的 DP。

使用完整数组快照时，要计入快照开销。若有 $M$ 段生效区间、$T$ 个时间点，简单实现的时间上界为：

$$O\bigl((M\log T+T)C\bigr).$$

可达性问题可以把其中的数组更新替换为 bitset。

洛谷练习

题目	训练重点
P4141 消失之物	独立删除一个物品后的方案计数。(Luogu)
AT_abc321_f #(subset sum = K) with Add and Erase	在线增删与计数逆转移。(Luogu)
P4095 Eden 的新背包问题	独立删除一整类多重物品。(Luogu)
CF601E A Museum Robbery	动态最大值背包，按生命区间离线处理。(Luogu)
CF981E Addition on Segments	区间生效与可达性，线段树加 bitset。(Luogu)

---

18. 超大容量完全背包与同余最短路

当目标上界巨大，但某个合适的模数较小时，可以不按实际容量开数组，而按余数建图。

这一方法尤其适合无限件物品的可表示性与大容量最优化。(OI Wiki)

18.1 可表示性：每个余数的最小可达数

设所有面值为正，取：

$$m=\min_i w_i.$$

定义：

$$d[r]=\text{能表示出来且模 }m\text{ 为 }r\text{ 的最小非负整数}.$$

图上有 $m$ 个点。每种面值 $w$ 对应边：

$$r\longrightarrow(r+w)\bmod m,$$

边权为 $w$。

从余数 0 出发跑 Dijkstra：

cpp
vector<ll> residue_dist(const vector<int>& a) {
    int m = *min_element(a.begin(), a.end());

    vector<ll> d(m, INF);
    priority_queue<pair<ll, int>,
                   vector<pair<ll, int>>,
                   greater<pair<ll, int>>> q;

    d[0] = 0;
    q.push({0, 0});

    while (!q.empty()) {
        auto [du, u] = q.top();
        q.pop();

        if (du != d[u]) continue;

        for (int w : a) {
            int v = (u + 1LL * w) % m;

            if (d[v] > du + w) {
                d[v] = du + w;
                q.push({d[v], v});
            }
        }
    }

    return d;
}

因为面值 $m$ 本身存在，余数 $r$ 下可表示的数恰好是：

$$d[r],\ d[r]+m,\ d[r]+2m,\ldots$$

所以不超过 $H$ 的可表示数数量为：

$$\sum_{r:d[r]\le H} \left( \left\lfloor\frac{H-d[r]}m\right\rfloor+1 \right).$$

注意这包含数字 0。

区间 $[L,R]$ 的答案就是：

$$\operatorname{count}(R)-\operatorname{count}(L-1).$$

18.2 边界处理

零面值不改变可表示的整数集合，可以先删除；若删完后没有正面值，则只有 0 可表示。

若某些余数永远不可达，就不能直接使用“最大不可表示数”的有限答案公式。对于全部余数可达的情形，各余数最后一个不可表示的候选为：

$$d[r]-m.$$

但“所有正整数都可表示时输出什么”“有无限多个不可表示数时输出什么”，要遵守题目约定。

P3403 从第 1 层开始，适合把目标平移为从 0 出发，并统计不超过 $h-1$ 的可达量。(Luogu)

18.3 超大容量求最大价值：最高性价比基准与约化费用

只有“按性价比贪心”并不正确，因为可能无法恰好装满。

设最高价值密度的物品为：

$$(m,p),$$

即对任意物品 $(w_i,v_i)$：

$$\frac{v_i}{w_i}\le\frac pm.$$

定义非负约化费用：

$$c_i=w_ip-v_im\ge0.$$

仍然按模 $m$ 建图，但边权改为 $c_i$。令 $d[r]$ 为到余数 $r$ 的最小约化费用。

一个总重量为 $V$、总价值为 $W$ 的方案满足：

$$Vp-Wm=\text{约化费用总和}.$$

于是，当容量足够大、最短路方案可以用基准物品补足时：

$$\boxed{ W_{\max}(V)=\frac{Vp-d[V\bmod m]}m }$$

其中一种充分条件为：

$$V\ge(m-1)\max_i w_i.$$

理由是可以选择一条不重复顶点的最短路，至多使用 $m-1$ 条边；其实际重量不超过右侧上界，然后补充若干件重量为 $m$ 的基准物品即可。

P9140 的数据范围正是为这种“大容量条件”设计的。完整实现见附件 huge_unbounded，其中对充分条件进行了断言检查。(Luogu)

洛谷练习

题目	训练重点
P3403 跳楼机	平移起点，统计可达楼层。(Luogu)
P2371 墨墨的等式	区间内可表示整数计数，注意零面值。(Luogu)
P2662 牛场围栏	构造可用长度，分析最大不可表示值。(Luogu)
P2737 麦香牛块 Beef McNuggets	最大不可表示整数与特殊输出约定。(Luogu)
P9140 背包	超大容量恰好装满的最大价值，约化费用最短路。(Luogu)

---

三、优化工具应如何选择

不要先问“这题能不能单调队列”，而应先写出正确状态与转移，再看瓶颈在哪里。

遇到的瓶颈或特征	优先考虑
只是二维阶段数组太大	滚动数组；先确认转移读旧层还是当前层
多重背包枚举数量太慢	二进制拆分；最值用单调队列，计数用滑动窗口和
只求一维非负和的可达性	bitset
容量很大、价值总和小	反向背包，以价值为状态
费用都接近一个巨大基数	件数加费用偏移
$n$ 很小、费用与价值都很大	折半搜索
无限件、容量巨大、模数较小	同余最短路
大量独立“缺一”询问	缺一分治
动态最值背包存在删除	生效区间离线、时间线段树、状态恢复
多项式形式的计数卷积	生成函数，必要时使用 NTT 与形式幂级数
转移有特殊凸性、Monge 性质等	在证明性质后考虑分治优化、斜率优化等

另外，有三个很实用但容易误用的预处理。

公因数缩放。 若所有费用均为 $g$ 的倍数，可以缩小费用维度。恰好装满时先检查 $C$ 是否能被 $g$ 整除；不超过容量时可使用 $\lfloor C/g\rfloor$。

截断无意义的容量。 0-1 背包没有必要开到超过所有可选物品总费用的容量。

区分“支配状态”和“支配物品”。 在同一阶段，一个状态费用更大、收益不高，可以在合适条件下被另一个状态支配；但不能因此随便删除一件“比另一件差”的 0-1 物品。

例如两件物品为：

$$(2,3),\quad(3,2),\qquad C=5.$$

第二件虽然更重、价值更低，但最优解会同时选择两件。删除第二件会把答案从 5 错误地降为 3。

---

四、最值得反复检查的错误

错误做法	问题所在
恰好装满的最大值 DP 全部初始化为 0	把不可达状态当成了合法状态
0-1 背包正序更新	同一件物品可能重复选择
完全背包倒序更新	变成了每种只能选一次
分组内每个选项直接更新同一个数组	可能选择同组多个选项，零费用尤其危险
二进制拆分后直接统计多重方案数	拆分表示可能不唯一
计数时不区分组合、排列和有标号副本	方案定义错误，转移再快也没有意义
最小费用覆盖仍按“不超过容量”理解	优化的可行域反了
有负增量仍机械套倒序循环	状态依赖方向可能改变或形成环
任意依赖 DAG 缩点后直接当树	共享前置条件可能被重复处理
树形背包不限制实际子树状态范围	平白增加大量无效合并
用一维可变前驱直接恢复历史方案	历史前驱可能已被后续物品覆盖
前 $K$ 优解一律去掉重复价值	不同方案可能允许价值相同
动态最大值背包模仿计数“减去物品”	max 已丢失必要信息，不可直接逆转
超大容量完全背包只按性价比贪心	无法保证恰好装满，也没有处理余数
看到卷积就上 NTT	最大加卷积不是普通乘加卷积

---

五、推荐的学习顺序

这不是难度评级，而是一条尽量减少前置知识断层的路线。

阶段	目标	建议题目顺序
第一阶段	掌握物品次数与循环方向	P1048 → P1049 → P1616 → P1776 → P1833
第二阶段	掌握状态含义与计数	P1757 → P1164 → P1474 → P1077 → P2392
第三阶段	掌握维度与约束转换	P1507 → AT_dp_e → P1510 → P2340 → P1651
第四阶段	掌握依赖与树上合并	P1064 → P1455 → P2014 → P2015 → P1273 → P2515
第五阶段	掌握附加目标与综合建模	P2066 → P1417 → P1759 → P1858 → P4377
第六阶段	掌握大规模与动态问题	P4799 → P1450 → P4141 → AT_abc321_f → P4095 → P3403 → P9140

学习每一道题时，建议固定写下五句话：

状态是什么；哪些状态初始可达；最后一次决策是什么；转移读取哪一层；答案从哪些状态中提取。

能清楚回答这五个问题，再加上对复杂度的估算，大部分背包变形就不再需要靠“见过同款题”来识别。

---

六、值得继续阅读的专题资料

《背包九讲》适合建立整体框架，特别是泛化物品、依赖关系与问法变化；OI Wiki 和 cp-algorithms 适合对照常用转移及优化。(GitHub)

洛谷文章《详解泛化物品解决树形依赖背包问题》适合理解为什么部分依赖背包不需要 $C^2$ 子树卷积；《树上背包时间复杂度证明》适合纠正“看见三重循环就认定 $O(nK^2)$”的习惯。(Luogu)

缺一分治专题、OI Wiki 同余最短路，以及 P9140、P4389 的相关题解，适合在基础模型熟练之后学习，它们分别把背包连接到分治、最短路和形式幂级数。(Luogu)

最终要形成的能力是：把复杂限制拆成状态，把合法选择拆成转移，把题目要求拆成合并运算。背包的“所有变形”，主要就从这三个位置生长出来。