GESP 题解库 / 6 级题解 / [GESP202512 六级] 道具商店 · 第 3 / 27 题
GESP202512 六级 · P14920 · 中等

道具商店

金币预算巨大(10⁹)时,如何做 0/1 背包——把 DP 维度换到价值上。

📊
n ≤ 500
道具数量
🔢
long long
数值类型
⚡
O(n × Σa)
时间复杂度
🎯
按"价值"做背包
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

道具商店有 n 件道具。第 i 件提升 aᵢ 点攻击力,需要 cᵢ 枚金币,每件只能购买一次。现有 k 枚金币,求最多能提升多少点攻击力。

💡
人话翻译:这是 0/1 背包,但背包容量 k 可达 10⁹,按容量开数组会爆内存。
注意数据特点:aᵢ ≤ 500 且 n ≤ 500,所以总攻击力 ≤ 250000——很小!所以把 DP 的维度换成"价值":求"恰好达到 v 点攻击力所需的最小金币数"。

🔍 关键词提取

0/1 背包维度互换min 型 DP大容量背包

已知条件

项目说明
输入第一行 n、k;随后 n 行 aᵢ、cᵢ
输出最多提升的攻击力
数据范围1 ≤ n ≤ 500
容量1 ≤ k ≤ 10⁹(很大!)
价值1 ≤ aᵢ ≤ 500(很小!)
花费1 ≤ cᵢ ≤ 10⁹

需要解决的问题

02
思维导图
整理解题思路的全貌
🔄 把 DP 维度从"容量"换到"价值"
🧠 常规背包
dp[容量] = 最大价值
容量 k 可达 10⁹
数组开不下
所以不能这样做
🔄 维度互换
改设 dp[价值] = 最小花费
价值总和 ≤ 250000
数组大小 = Σa + 1
完全可行
🔁 转移
对每件道具 (a, c)
v 从大到小遍历(0/1 背包)
dp[v] = min(dp[v], dp[v−a] + c)
取 min 而非 max
✅ 求答案
找满足 dp[v] ≤ k 的最大 v
从 Σa 往下扫
第一个满足的就是答案
(或全部扫描取最大)
03
样例手算推导
两个样例的 dp 推演

🧮 样例 1:n = 3,k = 5,道具 (99,1)、(33,2)、(11,3)

总攻击力 Σa = 99 + 33 + 11 = 143,所以 dp 数组大小取 144。

1
初始化

dp[0] = 0(凑 0 点攻击力花费 0)

其他 dp[v] = 无穷大(表示暂时无法凑出)

dp[0] = 0

2
加入道具 (99, 1)

v 从 143 递减到 99:

dp[99] = min(∞, dp[0] + 1) = 1

其他位置仍为 ∞

dp[99] = 1

3
加入道具 (33, 2)

dp[33] = dp[0] + 2 = 2

dp[132] = dp[99] + 2 = 3

其余不变

dp[33] = 2,dp[132] = 3

4
加入道具 (11, 3)

dp[11] = 3,dp[44] = dp[33]+3 = 5

dp[110] = dp[99]+3 = 4,dp[143] = dp[132]+3 = 6

其余不变

dp[143] = 6

5
找 dp[v] ≤ k = 5 的最大 v

v = 143:dp = 6 > 5 ✗

v = 132:dp = 3 ≤ 5 ✓

(110 的 dp = 4 也 ≤ 5,但 132 更大)

所以答案是 132

✅ 132

组合攻击力花费≤ k = 5?
99 + 33 + 111436✗
99 + 331323✓
99 + 111104✓
33 + 11445✓
99991✓

答案 132 ✓

🧮 样例 2:n = 4,k = 100,道具 (10,1)、(20,11)、(40,33)、(100,99)

这组数据里"单价"差异很大,正好体现背包的必要性。

组合攻击力花费≤ k = 100?
10010099✓
10 + 100110100✓
20 + 40 + 107045✓
20 + 100120110✗
40 + 100140132✗
10 + 20 + 100130111✗
20 + 40 + 10 + 100170144✗

答案 110 ✓

💡
注意本题更看重"总花费"而不是"单价"。虽然 (10, 1) 的性价比极高(10 攻击力只花 1 金币),但预算只有 100,所以必须靠 DP 枚举组合才能找到 110 这个最优值。贪心(按性价比排序)在 0/1 背包里是不保证正确的。
04
解法对比
按价值 DP vs 按容量 DP / 贪心

⚔️ 解法对比

🟢 按价值 DP(推荐) 推荐

dp[v] = 恰好凑出 v 点攻击力的最小花费,最后找 dp[v] ≤ k 的最大 v

  • 时间 O(n × Σa) ≤ 500 × 250000 = 1.25 × 10⁸
  • 空间 O(Σa) = 250001 个 long long(约 2 MB)
  • 转移取 min
  • 本质是 0/1 背包换维度
💡
为什么可以这样做:因为 Σaᵢ ≤ n × max(aᵢ) = 500 × 500 = 250000,价值维度很小。而容量 k 高达 10⁹,这种"容量大、价值小"的背包就是靠换维度解决的。

🟠 按容量 DP

dp[j] = 花费 ≤ j 时的最大攻击力,j 从 0 到 k

  • 数组需要 10⁹ + 1 个元素
  • 内存约 8 GB
  • 直接爆内存
  • 时间也不可能
⚠️
量级对比:容量维度 10⁹ vs 价值维度 2.5 × 10⁵——差了 4000 倍。背包题的维度选择 = 看"哪个范围小",这是最重要的解题判断。

📈 性能对比

方案空间可行性
按价值 DP约 2 MB✅ 可过
按容量 DP约 8 GB❌ 爆内存
贪心按性价比O(1)❌ 0/1 背包下不正确
05
算法流程图
按价值维度做 0/1 背包
开始读入 n、k 和各道具 (aᵢ, cᵢ);求和 = Σaᵢdp[0] = 0,dp[1..S] = 无穷大逐件处理道具 iv 从 S 递减到 aᵢdp[v] = min(dp[v], dp[v − aᵢ] + cᵢ)v 从 S 递减到 0,找到第一个 dp[v] ≤ k 的 v输出该 v处理下一件道具
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔄 道具商店背包

第一行输入 n 和 k,随后 n 行输入每件道具的攻击力与花费。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

const long long INF = 4e18;      // 足够大的"无穷"

long long dp[250005];            // dp[v] = 凑出 v 点攻击力的最小花费

int main() {
    int n;
    long long k;
    scanf("%d %lld", &n, &k);

    vector<int> a(n);
    vector<long long> c(n);
    int S = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d %lld", &a[i], &c[i]);
        S += a[i];                        // 总攻击力上限
    }

    // dp[0] = 0,其余为无穷大
    for (int v = 0; v <= S; v++) dp[v] = INF;
    dp[0] = 0;

    // 按价值维度做 0/1 背包
    for (int i = 0; i < n; i++) {
        for (int v = S; v >= a[i]; v--) {          // 倒序:保证每件只用一次
            if (dp[v - a[i]] + c[i] < dp[v])
                dp[v] = dp[v - a[i]] + c[i];
        }
    }

    // 找满足 dp[v] <= k 的最大 v
    for (int v = S; v >= 0; v--) {
        if (dp[v] <= k) { printf("%d\n", v); break; }
    }
    return 0;
}
🔑
为什么 v 要倒序遍历?这是 0/1 背包的标准技巧。倒序时 dp[v - a[i]] 还是"没考虑第 i 件"的旧值,保证每件道具最多用一次;若正序遍历,dp[v - a[i]] 可能已经用过了第 i 件,就变成"完全背包"(可以无限用)了。另外注意转移用的是 min(因为 dp 存的是最小花费)。

📖 关键几行怎么看

代码作用为什么这样写
S += a[i]价值上限数组只需开到总攻击力
dp[0] = 0,其余 INF初始化只有"凑 0 点"是免费可达的
for (v = S; v >= a[i]; v--)倒序遍历0/1 背包的关键
min(dp[v], dp[v-a[i]] + c[i])转移求最小花费
if (dp[v] <= k)答案从大到小找第一个可达的
⚠️
四个坑:① 按容量开数组(k 达 10⁹,爆内存);② 价值循环写成正序(变成完全背包);③ INF 设太小(cᵢ 可达 10⁹,加几次就超过 int 范围,要用 long long 的 4e18);④ 忘记 dp[0] = 0 的初始化。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 5
99 1 / 33 2 / 11 3
132题面样例 1:选 99 + 33
4 100
10 1 / 20 11 / 40 33 / 100 99
110题面样例 2:选 10 + 100
1 1
5 1
5刚好买得起
1 1
5 2
0买不起(花费 2 超过预算 1)
2 3
1 2 / 1 2
1只买得起一件
2 10
500 1000000000 / 1 1
1花费远大于预算,只能买便宜的
✅
自查清单:① 按价值开数组吗?② 倒序遍历吗?③ dp[0] = 0 初始化了吗?

🚨 易错点清单

⚠️
按容量 DP:k 可达 10⁹,数组开不下,必须把维度换到"价值"上。
⚠️
价值循环正序:会退化成"完全背包"(同一件可重复买),必须倒序。
⚠️
INF 太小:cᵢ 可达 10⁹,INF 要用 long long 的大值。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n × Σa)
空间复杂度
O(Σa)
最坏运算
≤ 500 × 250000 = 1.25 × 10⁸
数组大小
约 2 MB

时间怎么算的?

空间都用在哪?

dp[0..Σa],最多 250001 个 long long,约 2 MB。

✅ 约 1.25 亿次简单比较与加法,C++ 约 0.2 ~ 0.5 秒,可通过。如果卡常,可以只维护实际可达的状态(用 vector 去重)。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 0/1 背包两种维度的对比
// 按容量:dp[j] = 花费不超过 j 时的最大价值(j 为容量)
// 按价值:dp[v] = 达到价值 v 所需的最小花费(v 为价值)
// 选择依据:谁的取值范围小就用谁当维度

// 按价值维度的标准骨架
for (int v = 0; v <= S; v++) dp[v] = INF;
dp[0] = 0;
for (每个物品 i)
    for (int v = S; v >= a[i]; v--)          // 倒序!
        dp[v] = min(dp[v], dp[v - a[i]] + c[i]);
// 答案:满足 dp[v] <= k 的最大 v

// INF 的选取:要大于"任何可能的合法花费之和"
// 本题 c_i <= 10^9,n <= 500 -> 合法花费 <= 5 * 10^11
// 但为避免加法溢出,取 4e18(long long 的 1/4)较稳妥

// 空间优化:可以用两个 vector 或滚动数组
// 但本题价值维度不大,直接用一维数组即可

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
维度互换容量大就用价值当维度大容量、小价值的背包题
0/1 背包倒序保证每件只用一次所有 0/1 背包
min 型 DPdp 存最小花费"达到某价值的最小代价"类问题
🌟
思考题:如果题目改成"每件道具可以买无限多件",要改哪里?(提示:把价值循环改成正序即可——正序时 dp[v - a[i]] 可能已经用过第 i 件,正好实现了"重复购买"。倒序 = 0/1 背包,正序 = 完全背包,这是背包问题最经典的一个记忆点。)