很早之前在训练题单里看到“宠物小精灵之收服”这个标题我第一反应是模拟题读完题面才发现是个典型的动态规划而且压得挺深——表面上是抓精灵实际上考的是二维费用背包。题目不长你有若干精灵球有若干体力路上遇到一批野生精灵每只都要消耗一定数量的精灵球和一定体力才能收服。问最多能收服几只并且在收服数量最多的情况下最多还能剩下多少体力。适合刚学完01背包、准备往多维背包进阶的读者也适合拿来自测状态设计和循环边界。这篇文章我就从模型转化、状态设计、代码实现、常见坑和扩展思路几个方面把这道题完整拆开讲一遍。1. 先别急着写代码把题目翻译成背包模型1.1 题目到底在说什么先把题面抽象清楚。输入通常给三个数精灵球数量 N、体力值 M、野生精灵数量 K。接下来 K 行每行两个数 a、b表示收服这只精灵需要消耗 a 个精灵球、b 点体力。每只精灵只能被收服一次主角有初始的精灵搭档但这里跟 DP 转移无关不用管战斗过程。目标有两层第一优先级收服的精灵总数尽量多。第二优先级在收服数量已经最多的前提下体力的剩余值尽量大。这里有一个很容易忽略的限制体力不能归零更不能变成负数。说得严谨一点收服任意一只精灵之后剩余体力都必须大于 0。也就是说整个过程可消耗的体力上限不是 M而是 M - 1。比如体力上限是 10你最多只能消耗 9 点体力最后至少保留 1 点。举个最简单的例子帮助理解。假设精灵球 N 2体力 M 10野生精灵有两只精灵A消耗 2 个球、5 点体力。精灵B消耗 1 个球、4 点体力。球只有 2 个所以最多只能收服 1 只。如果收服 A剩余体力是 5如果收服 B剩余体力是 6。显然正确答案是收服 B输出应该是“1 6”。这个例子后面还能用来验证答案统计逻辑。把题目翻成算法语言就是经典的 0/1 背包变体有一批物品每件物品有两种“费用”每种费用都有上限每件物品价值为 1问在费用不超过上限的前提下能拿到的最大总价值是多少。因为每只精灵只能选一次所以是 01 背包不是完全背包。1.2 为什么是“二维费用”背包普通 01 背包只有一个约束背包容量。比如容量 W物品体积 w_i、价值 v_i。状态只需要一维 dp[j] 表示容量为 j 时的最大价值。这道题有两个独立的约束条件精灵球数量、体力值。每收服一只精灵两个约束都被消耗一部分所以状态里必须同时维护“用了多少个球”和“耗了多少体力”这就变成了二维费用背包。二维费用的本质就是把两个资源上限都作为状态维度。打个比方你负责选项目每个项目都要花钱、要占人力预算有限、人员也有限你希望项目总收益最大这跟抓精灵是一模一样的数学模型。只不过精灵的价值都是 1目标从“最大收益”变成“最大数量”。理解这一点之后自然就明白为什么不能用一维数组直接套 01 背包模板。如果你只保留 dp[j] 表示“用 j 个球”的最大数量你完全丢掉了体力信息只保留 dp[k] 表示“耗 k 点体力”的最大数量又会丢掉球数信息。两种费用都必须体现在状态里所以至少是二维数组。还有一个关键点K 只精灵这个维度不需要单独开状态。01 背包处理每件物品时从后往前更新天然保证了每件物品只被考虑一次所以精灵编号这一维可以直接压缩掉。这也是背包问题最常用的滚动思想后面我会再展开。1.3 一个最容易被忽略的约束体力不能归零很多初学者在这个地方翻车不是状态不会写而是体力边界搞错了。题目说体力小于等于 0 就不能继续收服所以任何合法方案的最后体力都必须大于等于 1。翻译成 DP 就是体力消耗量 k 的取值范围是 0 到 M - 1而不是 0 到 M。假如你把内层循环写成 k M那么以体力上限 M 10 为例dp[?][10] 这个状态表示消耗掉 10 点体力、最后体力是 0。从答案统计角度看这个状态可能让收服数量偏大因为它允许了一个题面不允许发生的“体力耗尽但还算收服成功”的情况。正确的做法是提前定一个变量int maxHealthCost M - 1;后面所有关于体力的循环、数组下标都用这个上限。最后输出剩余体力时再通过 M - minCost 换算回来。这样从源头上杜绝了“体力归零”的非法状态。如果 M 本身比较小比如 M 1那么 maxHealthCost 0意味着任何需要消耗体力的精灵都收服不了程序自然输出 0 和 1这个边界也是对的。2. 状态、转移和循环顺序一次说透2.1 状态定义用“恰好”还是“不超过”这个细节看着小实际影响整段代码的正确性和排查难度。我推荐把状态定义为dp[i][j] 表示恰好用掉 i 个精灵球、恰好消耗 j 点体力时能收服的最大精灵数量。为什么选“恰好”因为资源上限允许浪费也就是说最优解不一定把球和体力都用完。如果状态定义成“不超过”每次转移时都要额外考虑 dp[i-1][j] 和 dp[i][j-1] 的继承关系否则无法保证状态的单调性而定义成“恰好”之后最后从所有 i、j 范围内取最大值浪费资源的情况自然被覆盖了。使用“恰好”定义初始化必须小心。dp[0][0] 0 是合法起点一个球没用、一点体力没耗收服 0 只。其余所有 dp[i][j] 在开始处理任何精灵之前都应该是负无穷表示这个状态目前不可达。千万不要一股脑全部初始化为 0否则会凭空造出一堆非法状态后面统计答案时会出现“不去收服也能到达任何资源状态”的错觉导致结果偏大。如果你在别人的博客里看到初始化全 0 的写法也能 AC那是因为他们实际把状态理解成了“至多用了 i 个球、至多消耗 j 点体力”的松弛版本。但为了逻辑更严谨、更不容易出错我建议从负无穷初始化开始写一劳永逸。2.2 转移方程要这只精灵还是不要每来一只精灵你只有两种选择收服它或者不收服它。这是 01 背包的核心决策。设当前精灵消耗 a 个球、b 点体力那么转移方程是dp[i][j] max(dp[i][j], dp[i - a][j - b] 1)不收服保持 dp[i][j] 不变。收服必须保证 i a 且 j b用收服前的状态 dp[i - a][j - b] 加上这只精灵的数量 1。因为每只精灵只能收服一次所以处理完这只精灵之后所有状态的含义是“在考虑完已处理的这些精灵后恰好使用 i 个球、j 点体力”的最大数量。下一只精灵进来时更新就基于当前已经处理完上一批精灵的结果。这里有个细节值得解释为什么不用考虑收服的先后顺序因为每只精灵消耗的球数和体力都是固定的不管你先遇到谁、先抓谁总共消耗的量之和不变。背包问题只关心“选哪些”不关心“按什么顺序选”这正是它适合用 DP 的原因。如果你愿意可以把转移方程理解成“二维数组里的路径选择”要么停留在当前格子要么从左上某个位置跳过来跳一次就加 1。二维背包的图形化理解对初学者特别友好。2.3 双重逆序更新到底在防什么01 背包最关键的一行代码是内层循环要逆序。这道题有两个费用维度所以两个维度的循环都要逆序。为什么必须逆序用一只消耗 1 球、1 体力的精灵举例。初始 dp[0][0] 0。如果正序更新先算 dp[1][1] 1再算 dp[2][2] 时会看到 dp[1][1] 已经是 1结果 dp[2][2] 变成 2等于同一只精灵被收服了两次这显然不对。改成逆序之后先算 dp[2][2]此时 dp[1][1] 还是初始值负无穷所以 dp[2][2] 不会被更新接着算 dp[1][1] 才得到 1。这就保证了“当前这只精灵只能被使用一次”。二维费用背包里球数和体力两个维度都得逆序。因为两个维度都可能出现“更新后的状态被再次当作前驱”的问题。我习惯的写法是for (int i N; i a; --i) { for (int j maxHealthCost; j b; --j) { if (dp[i - a][j - b] ! NEG) { dp[i][j] max(dp[i][j], dp[i - a][j - b] 1); } } }外层循环是精灵球维度内层是体力维度两个都是从大到小跑。还有一个小陷阱如果某个精灵的体力消耗 b 为 0那么内层逆序仍然可能出问题因为 j - b 等于 j状态会发生自转移。大部分题目给的数据都是 b 1但如果题目没明确保证建议加一层判断或者在读入时过滤一下避免后面查错查到怀疑人生。3. 完整参考代码与答案统计的正确姿势3.1 先看一版能直接跑的 C 实现下面这版代码我用“恰好”语义配合负无穷初始化思路最清晰。题目常规数据范围是 N、M 都在 1000 以内K 在 100 左右直接开 1005 x 1005 的数组完全够用。#include bits/stdc.h using namespace std; const int NEG -1e9; int dp[1005][1005]; int main() { int N, M, K; cin N M K; vectorpairint, int p(K); for (int i 0; i K; i) { cin p[i].first p[i].second; } int maxHealthCost M - 1; // 至少保留 1 点体力 for (int i 0; i N; i) { for (int j 0; j maxHealthCost; j) { dp[i][j] NEG; } } dp[0][0] 0; for (int idx 0; idx K; idx) { int a p[idx].first; int b p[idx].second; for (int i N; i a; --i) { for (int j maxHealthCost; j b; --j) { if (dp[i - a][j - b] ! NEG) { dp[i][j] max(dp[i][j], dp[i - a][j - b] 1); } } } } int best 0; for (int i 0; i N; i) { for (int j 0; j maxHealthCost; j) { best max(best, dp[i][j]); } } int minCost 0; for (int j 0; j maxHealthCost; j) { bool flag false; for (int i 0; i N; i) { if (dp[i][j] best) { flag true; break; } } if (flag) { minCost j; break; } } cout best M - minCost endl; return 0; }代码里面的统计部分单独说几句。best 是全局最大收服数量遍历所有球数和体力消耗量取 max因为最优方案允许浪费球数也可能没有把体力消耗到上限。minCost 是“达到 best 这个数量时最少需要消耗的体力值”找到之后用 M - minCost 得到剩余体力正好对应题目要求。3.2 为什么最后要找最小体力消耗而不是直接算这是很多人觉得绕的地方。dp 数组里存的是最大数量同一个最大数量可能对应很多种体力消耗。比如我之前举的例子收服 A 消耗 5 体力收服 B 消耗 4 体力最后都是收服 1 只。如果你只找一个 dp[i][j] 等于 1 就收工很可能找到的是消耗 5 体力的方案剩余体力输出 5丢了 1 点体力。所以正确姿势是先确定 best 是多少然后从体力消耗最小的 j 0 开始往上扫一旦发现存在某个球数 i 满足 dp[i][j] best说明这个体力消耗量是可实现的而且因为是从小到大扫的它一定是最小消耗量。这个 j 就是 minCost剩余体力就是 M - minCost。这个“先数量、后消耗”的顺序就是题目里“收服最多并且剩余体力最大”的完整翻译。如果直接输出 dp[N][maxHealthCost] 对应的剩余体力在一些数据会错因为最优解可能根本没用完 N 个球。3.3 空间优化到底能省到什么程度很多初学者会问能不能把二维数组优化成一维坦率说二维费用背包一般不能再压成一维因为你必须同时记录两种资源的消耗量否则信息就丢了。真正能被滚动掉的是“精灵编号”这一维。如果把状态写成 dp[精灵编号][球数][体力]那就是三维数组空间复杂度 O(K * N * M)K 到 100、N 和 M 到 1000 时直接爆内存。但因为每只精灵只需要基于上一批精灵的结果更新而且循环逆序后当前精灵不会影响自己三维数组的第一维可以被完全去掉。空间复杂度从 O(K * N * M) 降到 O(N * M)这是这道题最核心的优化。再往下压就比较难了除非你有额外的约束或者改用记忆化搜索否则二维数组就是合理的内存下限。4. 新手最容易踩的五个坑4.1 体力上限多循环了一格最常见也最隐蔽的错误就是把体力循环写成 j M而正确写法是 j M - 1。表现是本地样例好像能过但数据一大或者特定样例就结果偏大因为你把“体力刚好耗尽”的非法状态算进去了。排查方法也简单把答案里输出剩余体力那一项检查一下如果出现剩余体力为 0 的最优解大概率就是这出了问题。遇到这种情况统一使用 maxHealthCost M - 1所有体力下标都以它为界。4.2 把 01 背包写成完全背包内层循环用了正序或者不小心把循环写成 j b 且 b 为 0都会导致同一只精灵被收服多次。表现是答案大得离谱甚至超过 K。我自己排查这类问题有个笨办法构造只有一只精灵的数据比如 N 10、M 10、K 1精灵消耗 1 球 1 体力。正确答案无论如何都不超过 1。如果程序输出 2 或 3那就是循环顺序写反了。这个测试数据简单粗暴几秒钟就能定位问题。4.3 答案只盯着 dp[N][M-1] 看因为状态是“恰好使用 N 个球、恰好消耗 M - 1 体力”最优方案很可能用不了这么多球所以 dp[N][M - 1] 可能并不是全局最优。正确答案可能藏在 dp[3][5] 这种看起来“没用完资源”的位置。解决办法就是我在参考代码里写的第一遍遍历所有球数 i 和所有体力消耗 j 取 max得到 best第二遍再按体力消耗从低到高找第一个能满足 dp[i][j] best 的 j。两道循环都别省。4.4 数组开小与越界二维数组开成 dp[N1][M1] 看起来没问题但如果你循环里写错了下标比如把 a 和 b 写反很容易出现越界。不同环境下越界表现不一样本地可能正常运行评测机可能直接 RE也可能静默覆盖其他内存产生随机错误。建议数组大小固定开成上限加 5比如 N、M 最多 1000 就开 1005别只开 1000。另外更新前一定要判断 dp[i - a][j - b] 是否等于 NEG这既防止不可达状态被使用也能避免一些负数下标问题——当然前提是循环边界已经保证了 i a、j b。4.5 边界数据一只都收服不了K 0或者每只精灵需要的球数和体力都超过上限这种情况程序要能正确输出“0 M”。我用负无穷初始化的版本处理得很好best 初始为 0minCost 从 0 开始扫dp[0][0] 0 一定等于 best所以输出就是 0 M。还有一种边界是 M 1maxHealthCost 0所有需要体力的精灵都抓不了同样自然覆盖。处理边界数据时不要依赖“我觉得题目不会这么出”评测数据最喜欢卡这种特判。5. 从这道题延伸出去有哪些变化5.1 多一维约束代码怎么改如果把题目改成每只精灵还会消耗一个“时间单位”而你总时间有限那这就是三维费用背包。状态变成 dp[i][j][t]表示用 i 个球、j 点体力、t 点时间能收服的最大数量。核心代码只需要再加一层循环for (int i N; i a; --i) { for (int j maxHealthCost; j b; --j) { for (int t maxTime; t c; --t) { if (dp[i - a][j - b][t - c] ! NEG) { dp[i][j][t] max(dp[i][j][t], dp[i - a][j - b][t - c] 1); } } } }思路完全一样但复杂度多乘一个时间上限。实际运用时要注意状态数量爆炸的问题如果三个资源上限都到 1000那三维数组就是 10 亿级别根本开不下。三维以上的费用背包在竞赛里已经算难题关键不是转移而是如何优化状态维度。5.2 这不是刷题玩具现实里就这么用二维费用背包在真实场景中非常常见。比如你要在有限预算和有限人力下选择一组开发任务希望总价值最高或者要在有限的仓储容量和物流成本下决定上架哪些商品。每项任务、每件商品就是“一只精灵”预算和人力就是“精灵球和体力”最终收益就是你要最大化的数量或金额。这类问题的难点往往不是 DP 本身而是能不能把业务约束准确地翻译成费用维度。如果某个资源约束非常隐蔽比如项目之间还有先后依赖那就不是单纯背包能解的需要引入拓扑序或者其他模型。能识别出“这是个二维费用背包”这件事本身就是能力。5.3 后续可以继续练哪些背包变体做完这道题我建议按顺序尝试这几类变体完全背包版每只精灵可以有无限个循环顺序改成顺序。要求“恰好消耗完某一资源”初始化状态和答案统计方式要调整。求方案数把 dp 从存最大值改成存方案数量转移用加法。分组背包多个精灵只能选一组中的一只状态多一层分组循环。多重背包每种精灵有数量限制需要二进制拆分优化。把这些变体串起来练你会发现自己对背包问题的理解不再是背模板而是真的能根据题目约束重新设计状态。二维费用背包是其中承上启下的一环搞明白它三维、分组这些只是换汤不换药。我个人还有个实操建议拿到这类题第一步永远是在草稿纸上画一个二维表格横轴是球数纵轴是体力消耗量然后手动模拟三只精灵的转移过程。状态定义的偏差、循环顺序的错误几乎都能在这个表格上直接看出来。这道题我前后写过好几遍每写一遍都对背包问题多一层理解。你把这篇文章里的代码自己敲一遍再跑几个小样例验证二维费用背包基本就稳了。 
长河君 · 2026/10/15 1:15:08 · 阅读 1.2k 宠物小精灵之收服：二维费用背包动态规划全解析
很早之前在训练题单里看到“宠物小精灵之收服”这个标题我第一反应是模拟题读完题面才发现是个典型的动态规划而且压得挺深——表面上是抓精灵实际上考的是二维费用背包。题目不长你有若干精灵球有若干体力路上遇到一批野生精灵每只都要消耗一定数量的精灵球和一定体力才能收服。问最多能收服几只并且在收服数量最多的情况下最多还能剩下多少体力。适合刚学完01背包、准备往多维背包进阶的读者也适合拿来自测状态设计和循环边界。这篇文章我就从模型转化、状态设计、代码实现、常见坑和扩展思路几个方面把这道题完整拆开讲一遍。1. 先别急着写代码把题目翻译成背包模型1.1 题目到底在说什么先把题面抽象清楚。输入通常给三个数精灵球数量 N、体力值 M、野生精灵数量 K。接下来 K 行每行两个数 a、b表示收服这只精灵需要消耗 a 个精灵球、b 点体力。每只精灵只能被收服一次主角有初始的精灵搭档但这里跟 DP 转移无关不用管战斗过程。目标有两层第一优先级收服的精灵总数尽量多。第二优先级在收服数量已经最多的前提下体力的剩余值尽量大。这里有一个很容易忽略的限制体力不能归零更不能变成负数。说得严谨一点收服任意一只精灵之后剩余体力都必须大于 0。也就是说整个过程可消耗的体力上限不是 M而是 M - 1。比如体力上限是 10你最多只能消耗 9 点体力最后至少保留 1 点。举个最简单的例子帮助理解。假设精灵球 N 2体力 M 10野生精灵有两只精灵A消耗 2 个球、5 点体力。精灵B消耗 1 个球、4 点体力。球只有 2 个所以最多只能收服 1 只。如果收服 A剩余体力是 5如果收服 B剩余体力是 6。显然正确答案是收服 B输出应该是“1 6”。这个例子后面还能用来验证答案统计逻辑。把题目翻成算法语言就是经典的 0/1 背包变体有一批物品每件物品有两种“费用”每种费用都有上限每件物品价值为 1问在费用不超过上限的前提下能拿到的最大总价值是多少。因为每只精灵只能选一次所以是 01 背包不是完全背包。1.2 为什么是“二维费用”背包普通 01 背包只有一个约束背包容量。比如容量 W物品体积 w_i、价值 v_i。状态只需要一维 dp[j] 表示容量为 j 时的最大价值。这道题有两个独立的约束条件精灵球数量、体力值。每收服一只精灵两个约束都被消耗一部分所以状态里必须同时维护“用了多少个球”和“耗了多少体力”这就变成了二维费用背包。二维费用的本质就是把两个资源上限都作为状态维度。打个比方你负责选项目每个项目都要花钱、要占人力预算有限、人员也有限你希望项目总收益最大这跟抓精灵是一模一样的数学模型。只不过精灵的价值都是 1目标从“最大收益”变成“最大数量”。理解这一点之后自然就明白为什么不能用一维数组直接套 01 背包模板。如果你只保留 dp[j] 表示“用 j 个球”的最大数量你完全丢掉了体力信息只保留 dp[k] 表示“耗 k 点体力”的最大数量又会丢掉球数信息。两种费用都必须体现在状态里所以至少是二维数组。还有一个关键点K 只精灵这个维度不需要单独开状态。01 背包处理每件物品时从后往前更新天然保证了每件物品只被考虑一次所以精灵编号这一维可以直接压缩掉。这也是背包问题最常用的滚动思想后面我会再展开。1.3 一个最容易被忽略的约束体力不能归零很多初学者在这个地方翻车不是状态不会写而是体力边界搞错了。题目说体力小于等于 0 就不能继续收服所以任何合法方案的最后体力都必须大于等于 1。翻译成 DP 就是体力消耗量 k 的取值范围是 0 到 M - 1而不是 0 到 M。假如你把内层循环写成 k M那么以体力上限 M 10 为例dp[?][10] 这个状态表示消耗掉 10 点体力、最后体力是 0。从答案统计角度看这个状态可能让收服数量偏大因为它允许了一个题面不允许发生的“体力耗尽但还算收服成功”的情况。正确的做法是提前定一个变量int maxHealthCost M - 1;后面所有关于体力的循环、数组下标都用这个上限。最后输出剩余体力时再通过 M - minCost 换算回来。这样从源头上杜绝了“体力归零”的非法状态。如果 M 本身比较小比如 M 1那么 maxHealthCost 0意味着任何需要消耗体力的精灵都收服不了程序自然输出 0 和 1这个边界也是对的。2. 状态、转移和循环顺序一次说透2.1 状态定义用“恰好”还是“不超过”这个细节看着小实际影响整段代码的正确性和排查难度。我推荐把状态定义为dp[i][j] 表示恰好用掉 i 个精灵球、恰好消耗 j 点体力时能收服的最大精灵数量。为什么选“恰好”因为资源上限允许浪费也就是说最优解不一定把球和体力都用完。如果状态定义成“不超过”每次转移时都要额外考虑 dp[i-1][j] 和 dp[i][j-1] 的继承关系否则无法保证状态的单调性而定义成“恰好”之后最后从所有 i、j 范围内取最大值浪费资源的情况自然被覆盖了。使用“恰好”定义初始化必须小心。dp[0][0] 0 是合法起点一个球没用、一点体力没耗收服 0 只。其余所有 dp[i][j] 在开始处理任何精灵之前都应该是负无穷表示这个状态目前不可达。千万不要一股脑全部初始化为 0否则会凭空造出一堆非法状态后面统计答案时会出现“不去收服也能到达任何资源状态”的错觉导致结果偏大。如果你在别人的博客里看到初始化全 0 的写法也能 AC那是因为他们实际把状态理解成了“至多用了 i 个球、至多消耗 j 点体力”的松弛版本。但为了逻辑更严谨、更不容易出错我建议从负无穷初始化开始写一劳永逸。2.2 转移方程要这只精灵还是不要每来一只精灵你只有两种选择收服它或者不收服它。这是 01 背包的核心决策。设当前精灵消耗 a 个球、b 点体力那么转移方程是dp[i][j] max(dp[i][j], dp[i - a][j - b] 1)不收服保持 dp[i][j] 不变。收服必须保证 i a 且 j b用收服前的状态 dp[i - a][j - b] 加上这只精灵的数量 1。因为每只精灵只能收服一次所以处理完这只精灵之后所有状态的含义是“在考虑完已处理的这些精灵后恰好使用 i 个球、j 点体力”的最大数量。下一只精灵进来时更新就基于当前已经处理完上一批精灵的结果。这里有个细节值得解释为什么不用考虑收服的先后顺序因为每只精灵消耗的球数和体力都是固定的不管你先遇到谁、先抓谁总共消耗的量之和不变。背包问题只关心“选哪些”不关心“按什么顺序选”这正是它适合用 DP 的原因。如果你愿意可以把转移方程理解成“二维数组里的路径选择”要么停留在当前格子要么从左上某个位置跳过来跳一次就加 1。二维背包的图形化理解对初学者特别友好。2.3 双重逆序更新到底在防什么01 背包最关键的一行代码是内层循环要逆序。这道题有两个费用维度所以两个维度的循环都要逆序。为什么必须逆序用一只消耗 1 球、1 体力的精灵举例。初始 dp[0][0] 0。如果正序更新先算 dp[1][1] 1再算 dp[2][2] 时会看到 dp[1][1] 已经是 1结果 dp[2][2] 变成 2等于同一只精灵被收服了两次这显然不对。改成逆序之后先算 dp[2][2]此时 dp[1][1] 还是初始值负无穷所以 dp[2][2] 不会被更新接着算 dp[1][1] 才得到 1。这就保证了“当前这只精灵只能被使用一次”。二维费用背包里球数和体力两个维度都得逆序。因为两个维度都可能出现“更新后的状态被再次当作前驱”的问题。我习惯的写法是for (int i N; i a; --i) { for (int j maxHealthCost; j b; --j) { if (dp[i - a][j - b] ! NEG) { dp[i][j] max(dp[i][j], dp[i - a][j - b] 1); } } }外层循环是精灵球维度内层是体力维度两个都是从大到小跑。还有一个小陷阱如果某个精灵的体力消耗 b 为 0那么内层逆序仍然可能出问题因为 j - b 等于 j状态会发生自转移。大部分题目给的数据都是 b 1但如果题目没明确保证建议加一层判断或者在读入时过滤一下避免后面查错查到怀疑人生。3. 完整参考代码与答案统计的正确姿势3.1 先看一版能直接跑的 C 实现下面这版代码我用“恰好”语义配合负无穷初始化思路最清晰。题目常规数据范围是 N、M 都在 1000 以内K 在 100 左右直接开 1005 x 1005 的数组完全够用。#include bits/stdc.h using namespace std; const int NEG -1e9; int dp[1005][1005]; int main() { int N, M, K; cin N M K; vectorpairint, int p(K); for (int i 0; i K; i) { cin p[i].first p[i].second; } int maxHealthCost M - 1; // 至少保留 1 点体力 for (int i 0; i N; i) { for (int j 0; j maxHealthCost; j) { dp[i][j] NEG; } } dp[0][0] 0; for (int idx 0; idx K; idx) { int a p[idx].first; int b p[idx].second; for (int i N; i a; --i) { for (int j maxHealthCost; j b; --j) { if (dp[i - a][j - b] ! NEG) { dp[i][j] max(dp[i][j], dp[i - a][j - b] 1); } } } } int best 0; for (int i 0; i N; i) { for (int j 0; j maxHealthCost; j) { best max(best, dp[i][j]); } } int minCost 0; for (int j 0; j maxHealthCost; j) { bool flag false; for (int i 0; i N; i) { if (dp[i][j] best) { flag true; break; } } if (flag) { minCost j; break; } } cout best M - minCost endl; return 0; }代码里面的统计部分单独说几句。best 是全局最大收服数量遍历所有球数和体力消耗量取 max因为最优方案允许浪费球数也可能没有把体力消耗到上限。minCost 是“达到 best 这个数量时最少需要消耗的体力值”找到之后用 M - minCost 得到剩余体力正好对应题目要求。3.2 为什么最后要找最小体力消耗而不是直接算这是很多人觉得绕的地方。dp 数组里存的是最大数量同一个最大数量可能对应很多种体力消耗。比如我之前举的例子收服 A 消耗 5 体力收服 B 消耗 4 体力最后都是收服 1 只。如果你只找一个 dp[i][j] 等于 1 就收工很可能找到的是消耗 5 体力的方案剩余体力输出 5丢了 1 点体力。所以正确姿势是先确定 best 是多少然后从体力消耗最小的 j 0 开始往上扫一旦发现存在某个球数 i 满足 dp[i][j] best说明这个体力消耗量是可实现的而且因为是从小到大扫的它一定是最小消耗量。这个 j 就是 minCost剩余体力就是 M - minCost。这个“先数量、后消耗”的顺序就是题目里“收服最多并且剩余体力最大”的完整翻译。如果直接输出 dp[N][maxHealthCost] 对应的剩余体力在一些数据会错因为最优解可能根本没用完 N 个球。3.3 空间优化到底能省到什么程度很多初学者会问能不能把二维数组优化成一维坦率说二维费用背包一般不能再压成一维因为你必须同时记录两种资源的消耗量否则信息就丢了。真正能被滚动掉的是“精灵编号”这一维。如果把状态写成 dp[精灵编号][球数][体力]那就是三维数组空间复杂度 O(K * N * M)K 到 100、N 和 M 到 1000 时直接爆内存。但因为每只精灵只需要基于上一批精灵的结果更新而且循环逆序后当前精灵不会影响自己三维数组的第一维可以被完全去掉。空间复杂度从 O(K * N * M) 降到 O(N * M)这是这道题最核心的优化。再往下压就比较难了除非你有额外的约束或者改用记忆化搜索否则二维数组就是合理的内存下限。4. 新手最容易踩的五个坑4.1 体力上限多循环了一格最常见也最隐蔽的错误就是把体力循环写成 j M而正确写法是 j M - 1。表现是本地样例好像能过但数据一大或者特定样例就结果偏大因为你把“体力刚好耗尽”的非法状态算进去了。排查方法也简单把答案里输出剩余体力那一项检查一下如果出现剩余体力为 0 的最优解大概率就是这出了问题。遇到这种情况统一使用 maxHealthCost M - 1所有体力下标都以它为界。4.2 把 01 背包写成完全背包内层循环用了正序或者不小心把循环写成 j b 且 b 为 0都会导致同一只精灵被收服多次。表现是答案大得离谱甚至超过 K。我自己排查这类问题有个笨办法构造只有一只精灵的数据比如 N 10、M 10、K 1精灵消耗 1 球 1 体力。正确答案无论如何都不超过 1。如果程序输出 2 或 3那就是循环顺序写反了。这个测试数据简单粗暴几秒钟就能定位问题。4.3 答案只盯着 dp[N][M-1] 看因为状态是“恰好使用 N 个球、恰好消耗 M - 1 体力”最优方案很可能用不了这么多球所以 dp[N][M - 1] 可能并不是全局最优。正确答案可能藏在 dp[3][5] 这种看起来“没用完资源”的位置。解决办法就是我在参考代码里写的第一遍遍历所有球数 i 和所有体力消耗 j 取 max得到 best第二遍再按体力消耗从低到高找第一个能满足 dp[i][j] best 的 j。两道循环都别省。4.4 数组开小与越界二维数组开成 dp[N1][M1] 看起来没问题但如果你循环里写错了下标比如把 a 和 b 写反很容易出现越界。不同环境下越界表现不一样本地可能正常运行评测机可能直接 RE也可能静默覆盖其他内存产生随机错误。建议数组大小固定开成上限加 5比如 N、M 最多 1000 就开 1005别只开 1000。另外更新前一定要判断 dp[i - a][j - b] 是否等于 NEG这既防止不可达状态被使用也能避免一些负数下标问题——当然前提是循环边界已经保证了 i a、j b。4.5 边界数据一只都收服不了K 0或者每只精灵需要的球数和体力都超过上限这种情况程序要能正确输出“0 M”。我用负无穷初始化的版本处理得很好best 初始为 0minCost 从 0 开始扫dp[0][0] 0 一定等于 best所以输出就是 0 M。还有一种边界是 M 1maxHealthCost 0所有需要体力的精灵都抓不了同样自然覆盖。处理边界数据时不要依赖“我觉得题目不会这么出”评测数据最喜欢卡这种特判。5. 从这道题延伸出去有哪些变化5.1 多一维约束代码怎么改如果把题目改成每只精灵还会消耗一个“时间单位”而你总时间有限那这就是三维费用背包。状态变成 dp[i][j][t]表示用 i 个球、j 点体力、t 点时间能收服的最大数量。核心代码只需要再加一层循环for (int i N; i a; --i) { for (int j maxHealthCost; j b; --j) { for (int t maxTime; t c; --t) { if (dp[i - a][j - b][t - c] ! NEG) { dp[i][j][t] max(dp[i][j][t], dp[i - a][j - b][t - c] 1); } } } }思路完全一样但复杂度多乘一个时间上限。实际运用时要注意状态数量爆炸的问题如果三个资源上限都到 1000那三维数组就是 10 亿级别根本开不下。三维以上的费用背包在竞赛里已经算难题关键不是转移而是如何优化状态维度。5.2 这不是刷题玩具现实里就这么用二维费用背包在真实场景中非常常见。比如你要在有限预算和有限人力下选择一组开发任务希望总价值最高或者要在有限的仓储容量和物流成本下决定上架哪些商品。每项任务、每件商品就是“一只精灵”预算和人力就是“精灵球和体力”最终收益就是你要最大化的数量或金额。这类问题的难点往往不是 DP 本身而是能不能把业务约束准确地翻译成费用维度。如果某个资源约束非常隐蔽比如项目之间还有先后依赖那就不是单纯背包能解的需要引入拓扑序或者其他模型。能识别出“这是个二维费用背包”这件事本身就是能力。5.3 后续可以继续练哪些背包变体做完这道题我建议按顺序尝试这几类变体完全背包版每只精灵可以有无限个循环顺序改成顺序。要求“恰好消耗完某一资源”初始化状态和答案统计方式要调整。求方案数把 dp 从存最大值改成存方案数量转移用加法。分组背包多个精灵只能选一组中的一只状态多一层分组循环。多重背包每种精灵有数量限制需要二进制拆分优化。把这些变体串起来练你会发现自己对背包问题的理解不再是背模板而是真的能根据题目约束重新设计状态。二维费用背包是其中承上启下的一环搞明白它三维、分组这些只是换汤不换药。我个人还有个实操建议拿到这类题第一步永远是在草稿纸上画一个二维表格横轴是球数纵轴是体力消耗量然后手动模拟三只精灵的转移过程。状态定义的偏差、循环顺序的错误几乎都能在这个表格上直接看出来。这道题我前后写过好几遍每写一遍都对背包问题多一层理解。你把这篇文章里的代码自己敲一遍再跑几个小样例验证二维费用背包基本就稳了。