1. 先拆个题：为什么叫"线性规划进阶"

第一次看到"CSP-线性规划进阶(背包dp专题）"这个标题的时候，估计不少人心里犯嘀咕：背包DP不是动态规划吗？怎么跟线性规划扯上关系了？说实话，这个命名放在竞赛圈里不算精确，但背后确实有点渊源。

线性规划研究的是在一组线性不等式约束下求线性目标函数的最值，比如工厂生产计划、运输调度这类问题。而背包DP处理的是一堆离散物品做"选/不选"决策，在容量约束下最大化总价值。两者的数学形式长得像：约束是线性的、目标是线性的，但线性规划里变量是连续的，背包的变量是0/1整数。所以严格说，背包是整数规划/离散优化，竞赛圈习惯叫它"线性规划进阶"，更多是指从连续优化跨度到离散决策这一层递进关系。

如果你正准备CSP-S（也就是通常说的提高级认证），背包DP几乎是必考、绕不开的专题。它太经典了，从最简单的01背包，到完全背包、多重背包、分组背包，再到树上背包、单调队列优化、方案数计数，变化多到一个专题能讲三天三夜。同时它又太容易出错了——初始化、循环顺序、取模、滚动数组覆盖，每个坑都能让你在考场上卡半小时。

这篇文章我从CSP备考视角重新梳理整个背包DP体系。不打算从"什么是动态规划"这种基础讲起，而是直接围绕四个经典模型、三个进阶优化套路、几种跨算法玩法和考场上真正管用的做题流程来写。适合已经会简单DP、想系统搞定背包专题的人；如果完全没接触过DP，建议先把LIS、数字三角形这类入门题刷明白再回头看。

2. 四大经典背包模型：递推关系与循环顺序的底层逻辑

2.1 01背包：倒序枚举容量的真正原因

01背包是所有背包问题的基础，一句话描述：每件物品只有一个，选或不选。

状态定义 dp[i][j] 表示前 i 件物品里选，总重量不超过 j 时的最大价值。转移就两句话：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

不选第 i 件，就是 dp[i-1][j]；选第 i 件，则从 dp[i-1][j-w[i]] 转移过来加价值。滚掉第一维后，代码长这样：

for (int i = 1; i <= n; i++) { for (int j = W; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } }

这里最关键的是容量 j 必须倒序枚举。我当年第一次写背包就把内层循环写成正序，结果出来一组完全背包的效果。原因很简单：正序枚举时，dp[j - w[i]] 可能已经在当前这一轮被更新过，相当于同一件物品被反复取用；倒序枚举时，dp[j - w[i]] 还停留在上一轮的状态，天然保证每件物品最多用一次。

2.2 完全背包：正序枚举的对称直觉

完全背包的物品可以无限取。转移方程形式上跟01背包一样，但含义变了：

dp[j] = max(dp[j], dp[j - w[i]] + v[i])

区别只在容量枚举方向从倒序改成正序：

for (int i = 1; i <= n; i++) { for (int j = w[i]; j <= W; j++) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } }

正序时，dp[j - w[i]] 是当前物品已经更新过的新状态，也就是说"当前这轮取完一次还能再取"，正好表达无限使用的语义。把01背包和完全背包放一起对比，就会发现一个漂亮的对称：01背包倒序是为了防止重复，完全背包正序是为了允许重复，本质上是同一套状态定义在不同循环方向下的自然结果。

2.3 多重背包：二进制拆分的数学依据

多重背包里第 i 种物品有 cnt[i] 件，每件重量 w[i]、价值 v[i]。最朴素的做法是把它拆成 cnt[i] 个01背包物品，复杂度 O(n * W * cnt)，遇到 cnt 很大必死。

二进制拆分解决的是"怎么用最少的新物品表达任意 1 到 cnt 件原物品的组合能力"。把 cnt 拆成 2^0、2^1、2^2……最后补一个余数。比如 cnt = 13，拆成 1、2、4、6（余数）。这四组分别代表"取1件、取2件、取4件、取6件原物品"的打包方案。因为任意 0 到 13 的整数都能由这四组数的某个子集凑出来，所以拆完后的01背包等价于原多重背包。

for (int i = 1; i <= n; i++) { int k = 1, remain = cnt[i]; while (remain > 0) { int take = min(k, remain); // 生成一个新物品：重量 take * w[i]，价值 take * v[i] // 放进 01 背包流程处理 remain -= take; k <<= 1; } }

为什么二进制拆分正确而不是十进制的1、10、100？因为我们要用"子集和"来覆盖连续整数区间，二进制下每个数都有唯一表示，拆出的组数最少，复杂度从 O(cnt) 降到 O(log cnt)。

2.4 分组背包：一组一组合并的视角

分组背包每组内有若干物品，组内只能选一个或不选。它的处理顺序很固定：先枚举组，再倒序枚举容量，最后枚举组内物品。

for (int g = 1; g <= groups; g++) { for (int j = W; j >= 0; j--) { for (int k = 0; k < siz[g]; k++) { if (j >= w[g][k]) dp[j] = max(dp[j], dp[j - w[g][k]] + v[g][k]); } } }

关键点在于容量倒序、组内物品正序。倒序保证这一组最多选一个物品，因为 dp[j - w[g][k]] 是"前 g-1 组"的状态，还没掺入当前组的决定。如果组内枚举放在 j 的外层，同一组内多个物品就可能被同时选上，结果就不对了。

四类模型的关系梳理成一张表，方便对照：

3. 进阶三板斧：单调队列、方案数与路径逆推

3.1 单调队列优化多重背包：从 O(nWm) 到 O(nW)

二进制拆分能把多重背包压到 O(nW log m)，但如果 m 和 W 都到 1e5，log 项还是有点悬。真正的线性做法是单调队列优化，这也是CSP提高组里少数能拉出区分度的背包考点。

核心推导过程是这样的。对第 i 种物品，设重量 w、价值 v、数量 c。状态转移可以写成：

dp[j] = max(dp[j - k*w] + k*v), 0 <= k <= min(c, j/w)

把所有 j 按模 w 的余数分类。令 r = j mod w，j = r + t*w，那么转移变成：

dp[r + t*w] = max(dp[r + (t-k)*w] + k*v) = t*v + max(dp[r + (t-k)*w] - (t-k)*v)

令 x = t - k，则 x 的范围是 [t - c, t]，问题转化为：对每个固定的 r，在滑动窗口 [t-c, t] 里取 dp[r + xw] - xv 的最大值。这就是经典滑动窗口最值，单调队列 O(1) 维护。

实现时注意两个细节：第一，每个余数 r 需要独立维护一个队列；第二，必须用上一轮物品的 dp 数组 pre 去查询窗口里的值，不能用当前轮已经更新过的 dp，否则会出现同一物品取超过 c 次的结果。

for (int i = 1; i <= n; i++) { int w = ww[i], v = vv[i], c = cc[i]; memcpy(pre, dp, sizeof(dp)); for (int r = 0; r < w; r++) { deque<int> q; for (int t = 0; r + t * w <= W; t++) { int cur = pre[r + t * w] - t * v; while (!q.empty() && pre[r + q.back() * w] - q.back() * v <= cur) q.pop_back(); q.push_back(t); while (!q.empty() && q.front() < t - c) q.pop_front(); dp[r + t * w] = pre[r + q.front() * w] + (t - q.front()) * v; } } }

第一次看懂这段代码的人大概率会愣一会儿。我的建议是把余数 r 固定成一个值，比如 w=3 时分别看 r=0、1、2，手推一遍 t 从 0 到 3 的过程，比盯着公式看十遍有效得多。

3.2 最优方案数：当"相等转移"出现时

考场上经常出现"求达到最大价值的方案数"这种延伸题。做法是在 dp 之外维护计数数组 cnt[j]，dp[j] 表示容量 j 的最大价值，cnt[j] 表示达到这个最大价值的方案数。

每次转移分三种情况处理：

if (dp[j] < dp[j - w[i]] + v[i]) { dp[j] = dp[j - w[i]] + v[i]; cnt[j] = cnt[j - w[i]]; } else if (dp[j] == dp[j - w[i]] + v[i]) { cnt[j] = (cnt[j] + cnt[j - w[i]]) % MOD; }

这个写法必须配合一个前提：cnt[0] = 1，其他初始为 0。边界含义是容量为0时，不选任何东西就是唯一合法方案。

我最开始写这类题踩过一个坑：如果方案数要对 1e9+7 取模，而我是先无脑加好几种再取模，中间值爆掉 long long 只能拿部分分。另外注意，如果题目要求"方案中物品编号不同就算不同方案"，那这个方法直接成立；如果要求"价值组合相同就算同一种方案"，那需要改成枚举价值的分类计数，完全另一个思路。

3.3 输出最优方案的逆推技巧

不要求最优值，而要求输出选了哪些物品的题，通常的解法是保留二维 dp 数组，然后从 dp[n][W] 倒推。

对 i 从 n 到 1，检查 dp[i][j] 的来源：

• 如果 dp[i][j] == dp[i-1][j]，说明可以不选第 i 件；
• 如果 dp[i][j] == dp[i-1][j - w[i]] + v[i]，说明选了第 i 件，把 i 记入答案，j 减去 w[i]。

两个条件同时成立时，说明选与不选价值一样，题目一般要求输出字典序最小的方案，这时候需要从 i=1 开始正向决定，而不是从 n 倒推。这个细节很多题解不会提，但真题里真的出现过。

如果要避免二维数组爆内存，可以用滚动数组提前存下每层的 dp 快照，或者用 bitset 记录每件物品在哪些容量下被选中。后一种方法空间大，但实现简单，适合小数据。

4. 背包不是孤岛：与树形DP、二分、期望的组合玩法

4.1 树上背包：有依赖关系的分组背包

CSP提高组的树形DP题里，选课模型是高频原型：每门课可能有先修课，选某门课必须先选它的先修课，总共最多选 m 门，求最大总学分。

这类问题的本质是"依赖背包"。把树的每个节点看作一个物品组，选这个节点后才有资格选择它的子节点。树上做分组背包的经典框架：

1. 对节点 u，初始化 f[u][1] = val[u]，f[u][0] = 0；
2. 对 u 的每个子结点 v，递归处理 v 的子树；
3. 把子树返回的结果当组内物品，用分组背包的方式合并进 f[u]。

合并代码骨架：

void dfs(int u, int fa) { f[u][1] = val[u]; // 至少选自己 for (int v : adj[u]) { if (v == fa) continue; dfs(v, u); for (int j = m; j >= 1; j--) { // 当前总选课数 for (int k = 1; k < j; k++) { // 分给子树的课数 f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]); } } } }

复杂度是 O(n * m^2)，m 是每个节点的容量上界。注意 j 倒序、k 正序，和分组背包保持一致的语义：每个子树最多合并一次。如果树上节点容量总和远小于 n*m，实际跑起来比理论快很多，因为并不是每个节点都有 m 种选择空间。

4.2 背包当二分的check函数

有一种题面长得完全不像背包，最后却用背包判断可行性。典型例子：给若干物品和总容量，问能否恰好凑出某个重量区间内的值；或者给一个数组，要求分割成若干段使每段和不超过 x 且段数最少，问 x 最小为多少。

碰到这种"求最小 x，使得某种约束可行"的问题，优先想二分答案。check 函数里需要判断"当前 x 下是否能完成目标"，此时往往套一个01背包或者完全背包：dp[j] 表示达成某种状态的最优代价，最后看目标容量是否可达。把背包当 check 用的好处是状态天然自带"选与不选"的组合语义，比纯贪心可靠得多。

我自己做题时总结过一个信号：题目里同时出现"每个物品只能用一次""最多/最少""恰好/至少"这些词，而数据范围又卡在 n≤200、W≤1e5 这种背包友好区间，那就很可能是背包+二分的题型。

4.3 期望DP里塞背包

期望类问题偶尔也和背包组队。比如某类抽卡/强化/合成场景：每次操作消耗固定资源，以概率 p 成功，失败则资源不退；问达到某个目标状态的最小期望消耗。这类题的 DP 维度往往包含"当前拥有资源量"或"当前合成等级"，转移时用背包的方式枚举资源分配。

遇到这种题我的经验是不要慌着套公式，先把状态定义写清楚：dp[i][j] 表示处理到第 i 步、当前容量为 j 时的最小期望消耗或最大成功概率。转移时把概率作为系数乘进去，注意枚举顺序仍然遵守对应背包模型的方向规则，概率不会改变"一件物品能用几次"这个本质。

5. CSP考场上的实战识别：数据范围决定算法选择

5.1 一眼认出背包题的特征清单

考场时间紧张，快速判断"这题该不该用背包"比会写代码更重要。我在训练里总结了一套识别清单，命中三条以上基本可以往背包方向想：

• 物品/任务/选项具有"选或不选"的二元语义，且数量有限；
• 存在一个明确的上限约束，比如容量、时间、预算、人数，这个上限能作为 DP 的一维；
• 目标是最大化或最小化某个总和指标；
• 约束和数据范围贴合典型背包复杂度，n 在 10^2 到 10^3 级别，上限在 10^4 到 10^5 级别；
• 物品之间有分组、依赖、数量限制等附加条件，常见的是多重或分组打包。

5.2 数据范围速查表

CSP-S 每题 1 秒时限，Python 选手要自动把复杂度预算减半。我常用的判断表如下：

最后两种是逆向思维：当容量太大撑不住数组，但物品价值总和很小的时候，把 DP 的维度从重量换成价值。dp[v] 存凑到价值 v 需要的最小重量，最后从大到小找第一个 dp[v] ≤ W 的值。这个技巧在CSP-S 2023 的某道题里出现过，算是近年比较重要的考点。

5.3 正确的对拍验证方法

背包题写出代码后，我最推荐的对拍方法是：写一个纯暴力 DFS 枚举所有选择方案，和 DP 结果对比随机小数据。数据范围开到 n≤15、W≤30，随机生成几百组。

对拍的核心价值不是抓"写错了"，而是抓"理解错了"。比如我遇到过一道题，题意实际是"总重量严格小于容量才算合法"，我写成小于等于；暴力枚举能立刻暴露这种语义偏差，而手造样例往往发现不了。对拍脚本里随机生成器要覆盖边界：w 最小等于 0、w 刚好等于 W、物品数量为 0、容量为 0。

6. 刷题路上真实踩过的坑和排查手记

6.1 初始化到底用 0 还是负无穷

这是背包题最容易翻车的点，没有之一。dp[j] 表示"重量不超过 j"时，初始化为 0 完全正确，代表背包空着也是合法状态；dp[j] 表示"重量恰好为 j"时，除 dp[0]=0 外必须初始化为负无穷，否则从空中转移出非法状态。

更隐蔽的是"至少装满容量"的变体，答案在 dp 数组的一段区间里取 min/max，而初始化直接决定你是否能把"超过容量一点点的方案"纳入统计。我见过不少选手三种语义混用一个模板，结果同一个代码换个题面就全错。建议每次写之前先在注释里写明本题目 dp 的语义，再决定初始化。

6.2 滚动数组的残留数据污染

用滚动数组时，j 的循环没覆盖到的位置会保留上一轮的旧值。表面上看起来"没变化"，其实已经污染了下一轮的状态。最典型的是 01 背包里 j < w[i] 的位置永远不被更新，如果某个 dp[j] 来自非常早的一轮且后面没有物品能更新它，那它就一直停留在"只考虑了前几个物品"的错误状态。

排查方法很笨但有效：在每次外层循环结束后，对所有 j 检查 dp[j] 是否单调不减（容量越大价值不应越小），一旦发现某段区间出现回退，立即检查是不是循环边界漏了。另一个稳妥做法是 dp 数组每次外层循环前 memset 成对应初始值，虽然多一次 O(W) 开销，但能消除一整类bug，CSP 考场完全值得。

6.3 完全背包里重量为0的危险

完全背包转移方程 dp[j] = max(dp[j], dp[j - w] + v)，如果 w = 0，那么 dp[j] 永远可以由 dp[j] 自己更新自己，加上 v 后无限增长，最后整张表全是垃圾值。01背包里 w=0 还好，因为倒序循环只会更新一次；完全背包正序循环配上 w=0 就是死循环的静态版本。

真实题目很少直接给出重量 0 的物品，但会有"花费为0"的操作，或者把容量拆成几部分导致某物品相对新容量为 0。遇到这种数据，要么特判 w=0 的物品统一计算贡献，要么把所有重量加一个偏移量再跑。我在一次模拟赛中就被这种数据坑到整题爆 0，从此在预处理里对 w=0 都单独处理。

6.4 long long 与取模时机

CSP 的背包题如果价值上界到 1e9，那么 dp 数组中间值可能超过 1e18，不开 long long 直接翻车。方案数题目要取模时，常见错误是"先累加后取模"导致中间值溢出。正确做法是每次加法后立即取模，但注意取模不能改变 dp 最大值的比较逻辑，dp 和 cnt 是两个数组，一个不取模一个取模，别混在一起计算。

6.5 单调队列的边界调试实录

我调试单调队列优化多重背包时犯过一个能写进教材的错误：窗口左边界用 t - c 判断，但 c 是"还能取的数量"，当 t - c 为负数时队列里存的 t 全部合法，我忘记处理负数导致队列被错误弹出。那次 debug 花了整整一个晚上，最后在草稿纸上手推了余数 r=1、w=3 的完整流程才发现。

给后来者的建议：单调队列问题不要光靠眼睛检查，先在草稿纸上选一个具体余数，t 从 0 开始一步步列窗口内容，把代码运行结果和手推结果对一边。十次里有九次能找到逻辑漏洞，剩下一次是变量名写串了。

6.6 多组数据重置遗漏

CSP 复赛的输入很少有多组数据，但平时训练和模拟题里经常有 T 组测试。多组数据时，dp 数组、cnt 数组、w 和 v 数组都要重置。我最常犯的一个错误是只重置了 dp，忘记重置 pre 数组，导致 memcpy 时把上一组数据的残留状态搬进了当前组。解决办法是自定义一个 clear() 函数，把所有全局数组统一清零，每次跑完一组就调用一次。

不知不觉写了这么多，回头看这个专题的坑基本都踩了一遍。背包DP充其量是CSP动态规划考核里的一个分支，但它的变种和组合能力确实强到值得单独花一整块时间吃透。如果你正在备赛，我的建议是先保证四大经典模型在不看板子的情况下手写通过，再逐步叠加单调队列、树上合并这些进阶技巧。遇到不会的变体别急着翻题解，试着从"选与不选、一个能用几次、一组选几个"这三个维度归因，大多数背包题都能对号入座。