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 的外层同一组内多个物品就可能被同时选上结果就不对了。四类模型的关系梳理成一张表方便对照模型每物可用次数容量循环方向复杂度常见坑01背包0或1次倒序O(nW)循环方向写反完全背包无限次正序O(nW)初始化INF与0混淆多重背包最多cnt次倒序二进制拆O(nW log cnt)拆组余数漏掉分组背包每组至多1件外层组、内层容量倒序O(nW)组内物品枚举位置错3. 进阶三板斧单调队列、方案数与路径逆推3.1 单调队列优化多重背包从 O(nWm) 到 O(nW)二进制拆分能把多重背包压到 O(nW log m)但如果 m 和 W 都到 1e5log 项还是有点悬。真正的线性做法是单调队列优化这也是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 wj 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) { dequeint 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 固定成一个值比如 w3 时分别看 r0、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时不选任何东西就是唯一合法方案。我最开始写这类题踩过一个坑如果方案数要对 1e97 取模而我是先无脑加好几种再取模中间值爆掉 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]。两个条件同时成立时说明选与不选价值一样题目一般要求输出字典序最小的方案这时候需要从 i1 开始正向决定而不是从 n 倒推。这个细节很多题解不会提但真题里真的出现过。如果要避免二维数组爆内存可以用滚动数组提前存下每层的 dp 快照或者用 bitset 记录每件物品在哪些容量下被选中。后一种方法空间大但实现简单适合小数据。4. 背包不是孤岛与树形DP、二分、期望的组合玩法4.1 树上背包有依赖关系的分组背包CSP提高组的树形DP题里选课模型是高频原型每门课可能有先修课选某门课必须先选它的先修课总共最多选 m 门求最大总学分。这类问题的本质是依赖背包。把树的每个节点看作一个物品组选这个节点后才有资格选择它的子节点。树上做分组背包的经典框架对节点 u初始化 f[u][1] val[u]f[u][0] 0对 u 的每个子结点 v递归处理 v 的子树把子树返回的结果当组内物品用分组背包的方式合并进 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 选手要自动把复杂度预算减半。我常用的判断表如下数据范围可行做法预估复杂度n ≤ 20状压DP/暴力枚举子集O(2^n * n)n ≤ 100, W ≤ 1e4标准01背包/完全背包O(nW)n ≤ 1e3, W ≤ 1e501背包加滚动数组注意常数优化O(nW) 1e8紧物品多且每种有数量多重背包优先二进制拆O(nW log cnt)W ≤ 30, n 很大把重量范围当容量倒过来做O(nW) 或 O(n * 价值范围)W 巨大无法开数组价值范围小则 dp[价值]最小重量O(n * 总价值)最后两种是逆向思维当容量太大撑不住数组但物品价值总和很小的时候把 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) 开销但能消除一整类bugCSP 考场完全值得。6.3 完全背包里重量为0的危险完全背包转移方程 dp[j] max(dp[j], dp[j - w] v)如果 w 0那么 dp[j] 永远可以由 dp[j] 自己更新自己加上 v 后无限增长最后整张表全是垃圾值。01背包里 w0 还好因为倒序循环只会更新一次完全背包正序循环配上 w0 就是死循环的静态版本。真实题目很少直接给出重量 0 的物品但会有花费为0的操作或者把容量拆成几部分导致某物品相对新容量为 0。遇到这种数据要么特判 w0 的物品统一计算贡献要么把所有重量加一个偏移量再跑。我在一次模拟赛中就被这种数据坑到整题爆 0从此在预处理里对 w0 都单独处理。6.4 long long 与取模时机CSP 的背包题如果价值上界到 1e9那么 dp 数组中间值可能超过 1e18不开 long long 直接翻车。方案数题目要取模时常见错误是先累加后取模导致中间值溢出。正确做法是每次加法后立即取模但注意取模不能改变 dp 最大值的比较逻辑dp 和 cnt 是两个数组一个不取模一个取模别混在一起计算。6.5 单调队列的边界调试实录我调试单调队列优化多重背包时犯过一个能写进教材的错误窗口左边界用 t - c 判断但 c 是还能取的数量当 t - c 为负数时队列里存的 t 全部合法我忘记处理负数导致队列被错误弹出。那次 debug 花了整整一个晚上最后在草稿纸上手推了余数 r1、w3 的完整流程才发现。给后来者的建议单调队列问题不要光靠眼睛检查先在草稿纸上选一个具体余数t 从 0 开始一步步列窗口内容把代码运行结果和手推结果对一边。十次里有九次能找到逻辑漏洞剩下一次是变量名写串了。6.6 多组数据重置遗漏CSP 复赛的输入很少有多组数据但平时训练和模拟题里经常有 T 组测试。多组数据时dp 数组、cnt 数组、w 和 v 数组都要重置。我最常犯的一个错误是只重置了 dp忘记重置 pre 数组导致 memcpy 时把上一组数据的残留状态搬进了当前组。解决办法是自定义一个 clear() 函数把所有全局数组统一清零每次跑完一组就调用一次。不知不觉写了这么多回头看这个专题的坑基本都踩了一遍。背包DP充其量是CSP动态规划考核里的一个分支但它的变种和组合能力确实强到值得单独花一整块时间吃透。如果你正在备赛我的建议是先保证四大经典模型在不看板子的情况下手写通过再逐步叠加单调队列、树上合并这些进阶技巧。遇到不会的变体别急着翻题解试着从选与不选、一个能用几次、一组选几个这三个维度归因大多数背包题都能对号入座。