很早之前在训练题单里看到“宠物小精灵之收服”这个标题，我第一反应是模拟题，读完题面才发现是个典型的动态规划，而且压得挺深——表面上是抓精灵，实际上考的是二维费用背包。题目不长：你有若干精灵球，有若干体力，路上遇到一批野生精灵，每只都要消耗一定数量的精灵球和一定体力才能收服。问最多能收服几只，并且在收服数量最多的情况下，最多还能剩下多少体力。适合刚学完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; vector<pair<int, 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[N+1][M+1] 看起来没问题，但如果你循环里写错了下标，比如把 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 初始为 0，minCost 从 0 开始扫，dp[0][0] = 0 一定等于 best，所以输出就是 0 M。

还有一种边界是 M = 1，maxHealthCost = 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 从存最大值改成存方案数量，转移用加法。
• 分组背包：多个精灵只能选一组中的一只，状态多一层分组循环。
• 多重背包：每种精灵有数量限制，需要二进制拆分优化。

把这些变体串起来练，你会发现自己对背包问题的理解不再是背模板，而是真的能根据题目约束重新设计状态。二维费用背包是其中承上启下的一环，搞明白它，三维、分组这些只是换汤不换药。

我个人还有个实操建议：拿到这类题，第一步永远是在草稿纸上画一个二维表格，横轴是球数，纵轴是体力消耗量，然后手动模拟三只精灵的转移过程。状态定义的偏差、循环顺序的错误，几乎都能在这个表格上直接看出来。这道题我前后写过好几遍，每写一遍都对背包问题多一层理解。你把这篇文章里的代码自己敲一遍，再跑几个小样例验证，二维费用背包基本就稳了。