从一道GESP六级真题出发：聊聊01背包的逆向思维

COCOgsta

158人浏览 · 2026-09-05 09:39:20

COCOgsta · 2026-09-05 09:39:20 发布

题源：洛谷 P14920 [GESP202512 六级] 道具商店
题目链接

1. 背景

背包问题是算法竞赛中最经典的动态规划模型之一，几乎每个学习DP的选手都会在某个时刻与它相遇。标准的01背包问题是这样的：有 $n$ 件物品，每件有重量 $w_i$ 和价值 $v_i$ ，给定背包容量 $C$ ，求能装下的最大总价值。状态定义通常是 $d p [j]$ 表示容量为 $j$ 时能获得的最大价值，转移时取 $dp[j] = \max(dp[j], dp[j-w_i] + v_i)$ 。

但本题偏偏不走寻常路。它把"预算 $k$ "放在容量位置，把"攻击力 $a_i$ "放在价值位置，看起来就是一个标准01背包——只不过容量 $k$ 可能很大，而攻击力之和却相对有限。于是就有了一个巧妙的逆向思路：把攻击力当作"重量"，把金币当作"成本"， $d p [j]$ 表示获得 $j$ 点攻击力所需的最小金币数，然后找所有 $\le k$ 中最大的 $j$ 。

这种"价值→容量，重量→成本"的互换，本质上是在问题空间中对偶——当原问题的"容量"维度过大但"价值"维度较小时，交换两个维度可以大幅降低时空开销。

本题在GESP六级中定位为"普及"难度，是01背包入门的经典例题，同时也是"逆向背包"思想的最佳示范。通过这道题，你不仅能掌握01背包的标准写法，还能理解"当预算太大时，把价值和容量互换"这一重要优化技巧。

2. 核心思想章节

2.1 传统背包 vs 逆向背包：从"求最大值"到"求最小值"

想象你去商店买东西，预算有限，想买总攻击力最高的组合。正常人的思路是：预算 $k$ 是容量，每件道具用掉一些金币，换来攻击力，求攻击力总和最大——这就是标准01背包，状态是 $dp[j] = $ 花费 $j$ 金币能获得的最大攻击力。

但如果预算 $k$ 非常大（比如 $10^9$ ），而道具数量不多、攻击力总和也不大（比如最多 $10^5$ ），那么标准背包的 $\cdot k)$ 就会直接炸掉。这时候我们换个角度想：我不关心"花多少钱获得多少攻击力"，而是关心"获得多少攻击力最少需要花多少钱"。

这个思路转变就像：你不是在问"我有100块钱能买多少东西"，而是在问"想买60块钱的东西最少需要多少钱"——前者是容量限制下的最大价值，后者是价值目标下的最小成本。两个问题是对偶的，哪个好算取决于哪个维度更小。

2.2 状态定义：攻击力作为"容量"，金币作为"价值"

逆向背包的状态定义是这样的：

$d p [j]$ ：获得恰好 $j$ 点攻击力所需的最小金币数。
初始状态： $d p [0] = 0$ ，其余 $\infty$ （表示不可达）。
转移方程：对于每件道具 $a_i, c_i)$ ，倒序遍历 $j$ 从 $s u m$ 到 $a_i$ ：
$dp[j] = \min(dp[j],\; dp[j - a_i] + c_i)$

这里 $s u m$ 是已经处理过的道具攻击力总和，动态增长的。 $d p [j]$ 的含义从"最大价值"变成了"最小成本"，但转移的逻辑本质没变——每件道具依然只有"选"与"不选"两种状态。

2.3 倒序遍历：保证每件道具只选一次

在01背包中，为了防止一件物品被重复使用，我们采用从大到小遍历 $j$ （即倒序遍历）。为什么？

假设 $j$ 从小到大遍历。处理当前物品 $(a, c)$ 时，如果先更新了 $d p [a]$ ，那么当 $j$ 到 $2 a$ 时， $d p [2 a]$ 可能会用 $d p [a]$ 来更新——而 $d p [a]$ 已经被当前物品更新过了，相当于这件物品被使用了两次。这变成了完全背包（物品无限次使用）。

而倒序遍历 $j$ 从大到小， $d p [j - a]$ 对应的下标比 $j$ 小，在倒序遍历中还没有被当前物品更新过（因为更小的下标在之后才遍历到），所以 $d p [j - a]$ 仍然是"未选当前物品"时的状态。这就保证了每件物品至多被选一次。

2.4 答案提取：扫描所有可达状态

DP 结束后， $d p [j]$ 记录了获得 $j$ 点攻击力的最小金币数。我们只需要遍历 $j = 0$ 到 $s u m$ （总攻击力上限），找出所有满足 $\le k$ 的 $j$ 中的最大值即可。

注意 $d p [j]$ 是"恰好"获得 $j$ 点攻击力的最小成本。如果某攻击力值无法达到， $d p [j]$ 保持为 $\infty$ ，自然不满足条件。如果我们想表达"至少获得 $j$ 点攻击力"的最小成本，需要额外处理，但本题中"恰好"和"至少"在最终取最大值时没有区别——因为如果能够获得超过 $j$ 的攻击力，那 $j$ 本身也一定可达？不一定，但最大值一定落在某个恰好可达的攻击力值上，所以扫 $\max$ 是安全的。

小结：逆向背包的核心是"价值"与"成本"的对偶互换。当预算维度远大于价值总和时，把价值当容量、成本当价值，可以大幅降低复杂度。倒序遍历是一维01背包的通用技巧，保证每件物品只选一次。

3. 算法模板章节

3.1 算法到底在干什么？—— 直觉解释

你有一张购物清单，每件商品标着"攻击力加成"和"价格"。你不关心具体花了多少钱，只想知道：在不超过预算 $k$ 的前提下，能买到的最高攻击力是多少。

但预算 $k$ 太大了（比如10亿），你不能按"1块钱、2块钱、3块钱……"这样去枚举所有可能的消费金额。但攻击力总和可能很小（比如所有道具攻击力加起来才500），于是你反过来想：我不按"钱"分类，而是按"攻击力"分类—— $d p [j]$ 表示凑出 $j$ 点攻击力最少要花多少钱。

这样你只需要开一个大小为"总攻击力"的数组，而不是大小为"预算"的数组。算完所有 $d p [j]$ 后，从高到低看哪个 $\le k$ ，就是答案。

3.2 万能模板 —— 伪代码 + 实战代码

伪代码：

读入 n, k
sum = 0
dp[0] = 0, dp[1..MAX] = INF

for i = 1..n:
    读入 a[i], c[i]
    sum += a[i]
    for j = sum downto a[i]:
        dp[j] = min(dp[j], dp[j - a[i]] + c[i])

ans = 0
for j = 0..sum:
    if dp[j] <= k:
        ans = max(ans, j)
输出 ans

完整 AC 代码（C++，带注释）：

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

#define int long long
const int N = 505;           // 道具数量上限
int n, k;                    // n: 道具数, k: 预算
int a[N], c[N];              // a[i]: 攻击力, c[i]: 金币花费
int dp[N * N];               // dp[j]: 获得恰好 j 攻击力的最小金币数
int sum;                     // 所有道具攻击力之和
int ans;                     // 最终答案

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 初始化：只有 0 攻击力可达，成本为 0
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> c[i];
    }

    // 逆向01背包：以攻击力为"容量"，以金币为"价值"
    for (int i = 1; i <= n; i++) {
        sum += a[i];  // 动态更新攻击力上限

        // 倒序遍历，保证每件道具只选一次
        for (int j = sum; j >= a[i]; j--) {
            // 不选：保持 dp[j]；选：花费 c[i] 金币，获得 a[i] 攻击力
            dp[j] = min(dp[j], dp[j - a[i]] + c[i]);
        }
    }

    // 在预算 k 内找到能获得的最大攻击力
    for (int j = 0; j <= sum; j++) {
        if (dp[j] <= k) {
            ans = max(ans, j);
        }
    }

    cout << ans << endl;
    return 0;
}

3.3 例题实现 —— 本题完整运行流程

以样例为例：

n=3, k=5
道具1: a=99, c=1
道具2: a=33, c=2
道具3: a=11, c=3

DP 过程：

初始：dp[0] = 0，其余 INF
处理道具1 (99, 1)：sum=99，倒序 j=99：dp[99] = dp[0] + 1 = 1
处理道具2 (33, 2)：sum=132，倒序：
- j=132：dp[132] = dp[99] + 2 = 3
- j=99：dp[99] = min(1, dp[66] + 2) = 1（不变）
- j=33：dp[33] = dp[0] + 2 = 2
处理道具3 (11, 3)：sum=143，倒序：
- 会组合出更多攻击力值，如 143 = 99+33+11，成本 1+2+3=6
- 110 = 99+11，成本 1+3=4；44 = 33+11，成本 2+3=5
- 等等

答案提取：

dp[132] = 3 <= 5 → 攻击力 132 可达，成本3
dp[143] = 6 > 5 → 不可达
遍历所有 $j$ ，最大满足条件的 $j = 132$

输出 132，与样例一致。✅

3.4 对比实现 —— 如果使用标准01背包会怎样？

标准01背包：dp[j] 表示花费 $j$ 金币能获得的最大攻击力， $j$ 的范围是 $\sim k$ 。

如果 $k = 5$ ，标准背包非常简单： $d p [0..5]$ ，容量很小，直接 O(n*k) 就能算完。但如果 $k=10^9$ ，标准背包数组就开不下了—— $10^9$ 个 long long 需要 8GB 内存，完全不可行。

而逆向背包的数组大小是 $\sum a_i$ ，即所有道具攻击力之和。如果道具数量 $\le 500$ ，每个 $a_i \le 500$ ，总攻击力 $\le 250000$ ，数组大小完全可控。

所以，选择正向还是逆向，取决于两个维度哪个更小：

若 $k$ 较小（预算有限），用标准01背包： $d p [0.. k]$ 。
若 $\sum a_i$ 较小（攻击力总和有限），用逆向背包： $dp[0..\sum a_i]$ 。

本题的代码采用了逆向背包，因为 $n$ 和 $a_i$ 的范围通常使得 $\sum a_i$ 远小于 $k$ 的上界。

3.5 变体清单

变体场景	处理方法	与本题的差异
每件道具可以买多次（完全背包）	正向遍历 $j$ 从 $a_i$ 到 $s u m$ ，而非倒序	本题每件只能买一次
预算 $k$ 较小，直接用标准01背包	$d p [j]$ 为花费 $j$ 金币的最大攻击力，正向或倒序均可	本题用逆向背包
需要输出具体选了哪些道具	在 DP 中记录决策来源（pre 数组），最后回溯	本题只求最大值
攻击力可能为 0	无影响， $a_i > 0$ 是题目的隐含保证	—
道具数量很多但攻击力总和仍然很小	逆向背包仍然高效	—
要求总攻击力恰好等于某个值	答案提取时只取 $\le k$ 且 $d p [j]$ 可达的 $j$	本题目标是"不超过预算下的最大攻击力"
每件道具不仅有价格还有重量（二维背包）	需要二维 DP，或者将重量压缩到状态中	本题只有一维约束（金币）

3.6 什么时候不能用？

攻击力总和也很大：如果 $\sum a_i$ 同样达到 $10^6$ 甚至 $10^7$ ，数组可能仍然过大，需要考虑其他优化（如折半搜索、贪心+DP剪枝等）。
需要同时满足多个约束：例如既有金币限制又有重量限制，需要二维背包，此时逆向思维无法简单扩展。
$a_i$ 和 $c_i$ 的范围差异极大：如果攻击力 $a_i$ 很大但 $n$ 很小， $\sum a_i$ 可能超出数组范围。但通常 $\le 500, a_i \le 500$ ，这是安全的。
物品数量极大（ $\ge 10^5$ ）且攻击力总和很大：此时 DP 的 $\cdot \sum a_i)$ 无法承受，需考虑其他算法（如贪心+DP混合，或使用bitset优化）。

4. 底层逻辑章节

4.1 为什么逆向 DP 是正确的？

逆向 DP 的正确性来源于问题的对偶性。我们想要最大化 $\sum a_i x_i$ ，约束为 $\sum c_i x_i \le k$ ，其中 $x_i \in \{0,1\}$ 。

标准背包 DP 是固定一个"成本阈值" $j$ ，求最大"价值"：
$\max \left\{ \sum a_i x_i \;\middle|\; \sum c_i x_i \le j \right\}$

逆向背包 DP 是固定一个"价值目标" $j$ ，求最小"成本"：
$\min \left\{ \sum c_i x_i \;\middle|\; \sum a_i x_i = j \right\}$

这两个问题在数学上是等价的，因为：

如果标准背包求出了 $f [k] = V$ ，那么逆向背包中 $\le k$ 且对于任意 $V^{'} > V$ ， $g [V^{'}] > k$ 。
反之，如果逆向背包求出了对于所有 $j$ 的 $g [j]$ ，那么 $\max\{j \mid g[j] \le k\}$ 。

所以，使用逆向背包并不会丢失任何信息，只是换了一个角度计算同一个问题的解。

4.2 为什么倒序遍历能保证"每件只选一次"？

这是一个一维01背包的经典知识点。考虑二维 DP 的转移：
$dp[i][j] = \min(dp[i-1][j],\; dp[i-1][j-a_i] + c_i)$
其中 $d p [i - 1] [*]$ 表示只考虑前 $i - 1$ 件物品时的状态。

压缩到一维后， $d p [j]$ 在遍历到第 $i$ 件物品时，我们希望 $dp[j-a_i]$ 仍然是"只考虑前 $i - 1$ 件"的状态。如果 $j$ 从小到大遍历， $dp[j-a_i]$ 可能已经被第 $i$ 件物品更新过了（因为 $j-a_i < j$ ，在从小到大遍历中已经被处理），这就相当于物品被使用了多次。

如果 $j$ 从大到小遍历， $j-a_i$ 在 $j$ 之后才会被遍历到，所以 $dp[j-a_i]$ 还没有被第 $i$ 件物品更新，保持了"前 $i - 1$ 件"的状态。这就保证了每件物品只用一次。

4.3 与完全背包的对比

完全背包允许每件物品无限次使用，转移方程与01背包的区别仅在于遍历顺序：

01背包：for j = sum downto a[i]
完全背包：for j = a[i] to sum

完全背包中从小到大遍历， $dp[j-a_i]$ 已经被当前物品更新过，相当于物品可以被多次叠加。如果错用了遍历顺序，01背包会变成完全背包（或反之），导致答案错误。这是背包类问题中最常见的 Bug 之一。

5. 决策表：不同思路的适用场景

场景	方案	时间复杂度	空间复杂度	优点	缺点
预算 $k$ 较小（ $\le 10^5$ ）	标准01背包（容量为 $k$ ）	$\cdot k)$	$O (k)$	直观，直接求最大攻击力	$k$ 大时不可行
攻击力总和 $\sum a_i$ 较小（ $\le 10^6$ ）	逆向01背包（容量为 $\sum a_i$ ）	$\cdot \sum a_i)$	$O(\sum a_i)$	适用于大预算场景	攻击力总和过大时不可行
两者都很大	折半搜索（meet-in-the-middle）	$O(2^{n/2} \cdot \text{sort})$	$O(2^{n/2})$	可处理 $\le 40$ 的大值场景	指数级， $n$ 不能太大
物品数量 $n$ 极大但 $a_i$ 很小	多重背包 + 二进制优化	视具体情况	视具体情况	可处理大量重复物品	本题 $n$ 较小，不需要
需要求"至少 $V$ 攻击力的最小成本"	逆向 DP 后做后缀最小值	$\cdot \sum a_i + \sum a_i)$	$O(\sum a_i)$	直接回答查询	本题不需要

6. 工程视角

"价值↔成本对偶"的背包思想在实际工程中也有大量应用：

云计算资源采购：云服务商提供多种实例规格，每种规格有计算能力（价值）和价格（成本），预算有限时求最大计算能力。如果价格范围很大但计算能力总和较小，可以采用逆向思路。
广告投放中的预算分配：多个广告位有不同点击量和出价，预算限制下最大化点击量。当出价范围大时，用点击量做 DP 维度更高效。
项目投资组合优化：每个项目有预期收益和投资额，资金有限时最大化总收益。资金总额可能很大，但收益总和相对可控。
代码优化中的"时间换空间"：在算法设计中，如果内存限制宽松但时间紧张，可以用空间换时间；如果内存紧张但时间充裕，逆向 DP 用较小的空间换取稍大的时间复杂度（但依然可控）。
库存管理中的采购决策：每种原材料有库存成本和加工收益，预算有限时最大化加工收益。当原材料种类不多但预算规模很大时，逆向 DP 是自然的选型。

7. 小结

核心公式：

逆向01背包的状态转移：
$\min(dp[j],\; dp[j - a_i] + c_i), \quad j = \text{sum} \to a_i$
其中 $d p [j]$ 表示获得恰好 $j$ 点攻击力的最小金币数。

最终答案：
$\text{ans} = \max\{j \mid dp[j] \le k\}$

核心认知：

01背包有两种等价视角：容量限制下的最大价值（标准）和价值目标下的最小成本（逆向）。选择哪个取决于哪个维度更小。
倒序遍历是01背包一维压缩的关键，保证每件物品只选一次。记清楚"倒序是01，正序是完全"。
逆向背包的答案提取是扫描所有可达状态，取满足预算约束的最大值——这个操作的复杂度是 $O(\sum a_i)$ ，远小于标准背包的 $O (k)$ 在大预算场景下的开销。
这道题教会我们：当问题的某个维度过大而另一个维度较小时，不要死守标准的 DP 方向，尝试对偶互换往往会带来惊喜。