金币预算巨大(10⁹)时,如何做 0/1 背包——把 DP 维度换到价值上。
道具商店有 n 件道具。第 i 件提升 aᵢ 点攻击力,需要 cᵢ 枚金币,每件只能购买一次。现有 k 枚金币,求最多能提升多少点攻击力。
0/1 背包维度互换min 型 DP大容量背包
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 n、k;随后 n 行 aᵢ、cᵢ |
| 输出 | 最多提升的攻击力 |
| 数据范围 | 1 ≤ n ≤ 500 |
| 容量 | 1 ≤ k ≤ 10⁹(很大!) |
| 价值 | 1 ≤ aᵢ ≤ 500(很小!) |
| 花费 | 1 ≤ cᵢ ≤ 10⁹ |
dp[k] 需要 10⁹ 大小的数组,内存和时间都不允许dp[v] = 恰好凑出 v 点攻击力的最小花费;答案是满足 dp[v] ≤ k 的最大 vΣaᵢ ≤ 500 × 500 = 250000,完全可行总攻击力 Σa = 99 + 33 + 11 = 143,所以 dp 数组大小取 144。
dp[0] = 0(凑 0 点攻击力花费 0)
其他 dp[v] = 无穷大(表示暂时无法凑出)
dp[0] = 0
v 从 143 递减到 99:
dp[99] = min(∞, dp[0] + 1) = 1
其他位置仍为 ∞
dp[99] = 1
dp[33] = dp[0] + 2 = 2
dp[132] = dp[99] + 2 = 3
其余不变
dp[33] = 2,dp[132] = 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
v = 143:dp = 6 > 5 ✗
v = 132:dp = 3 ≤ 5 ✓
(110 的 dp = 4 也 ≤ 5,但 132 更大)
所以答案是 132
✅ 132
| 组合 | 攻击力 | 花费 | ≤ k = 5? |
|---|---|---|---|
| 99 + 33 + 11 | 143 | 6 | ✗ |
| 99 + 33 | 132 | 3 | ✓ |
| 99 + 11 | 110 | 4 | ✓ |
| 33 + 11 | 44 | 5 | ✓ |
| 99 | 99 | 1 | ✓ |
答案 132 ✓
这组数据里"单价"差异很大,正好体现背包的必要性。
| 组合 | 攻击力 | 花费 | ≤ k = 100? |
|---|---|---|---|
| 100 | 100 | 99 | ✓ |
| 10 + 100 | 110 | 100 | ✓ |
| 20 + 40 + 10 | 70 | 45 | ✓ |
| 20 + 100 | 120 | 110 | ✗ |
| 40 + 100 | 140 | 132 | ✗ |
| 10 + 20 + 100 | 130 | 111 | ✗ |
| 20 + 40 + 10 + 100 | 170 | 144 | ✗ |
答案 110 ✓
(10, 1) 的性价比极高(10 攻击力只花 1 金币),但预算只有 100,所以必须靠 DP 枚举组合才能找到 110 这个最优值。贪心(按性价比排序)在 0/1 背包里是不保证正确的。dp[v] = 恰好凑出 v 点攻击力的最小花费,最后找 dp[v] ≤ k 的最大 v
O(Σa) = 250001 个 long long(约 2 MB)Σaᵢ ≤ n × max(aᵢ) = 500 × 500 = 250000,价值维度很小。而容量 k 高达 10⁹,这种"容量大、价值小"的背包就是靠换维度解决的。dp[j] = 花费 ≤ j 时的最大攻击力,j 从 0 到 k
| 方案 | 空间 | 可行性 |
|---|---|---|
| 按价值 DP | 约 2 MB | ✅ 可过 |
| 按容量 DP | 约 8 GB | ❌ 爆内存 |
| 贪心按性价比 | O(1) | ❌ 0/1 背包下不正确 |
第一行输入 n 和 k,随后 n 行输入每件道具的攻击力与花费。
点按钮开始 →
#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) | 答案 | 从大到小找第一个可达的 |
INF 设太小(cᵢ 可达 10⁹,加几次就超过 int 范围,要用 long long 的 4e18);④ 忘记 dp[0] = 0 的初始化。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
3 5 | 132 | 题面样例 1:选 99 + 33 |
4 100 | 110 | 题面样例 2:选 10 + 100 |
1 1 | 5 | 刚好买得起 |
1 1 | 0 | 买不起(花费 2 超过预算 1) |
2 3 | 1 | 只买得起一件 |
2 10 | 1 | 花费远大于预算,只能买便宜的 |
cᵢ 可达 10⁹,INF 要用 long long 的大值。dp[0..Σa],最多 250001 个 long long,约 2 MB。
✅ 约 1.25 亿次简单比较与加法,C++ 约 0.2 ~ 0.5 秒,可通过。如果卡常,可以只维护实际可达的状态(用 vector 去重)。
// 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 型 DP | dp 存最小花费 | "达到某价值的最小代价"类问题 |
dp[v - a[i]] 可能已经用过第 i 件,正好实现了"重复购买"。倒序 = 0/1 背包,正序 = 完全背包,这是背包问题最经典的一个记忆点。)