每种饮料至多买一瓶,使总容量 ≥ L 且花费最少。
商店有 N 种饮料,第 i 种售价 cᵢ、容量 lᵢ。要求:每种至多买 1 瓶;总容量 ≥ L;在此前提下花费最少。若无论如何都满足不了容量要求,输出 no solution。
dp[v] = 让总容量恰好达到 v 所需的最少费用,其中容量超过 L 的一律"压"到 L 上(因为我们只关心"够不够",不关心超出多少)。dp[L];若它仍是"无穷大"就说明无解。0/1 背包最小费用容量上限压缩无解判定
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N、L;随后 N 行每行 cᵢ、lᵢ |
| 输出 | 最少费用,或 no solution |
| 数据范围 | 1 ≤ N ≤ 500,1 ≤ L ≤ 2000 |
| 花费/容量 | 1 ≤ cᵢ, lᵢ ≤ 10⁶ |
| 目标 | 总容量 ≥ L 且费用最小 |
dp[min(L, v + lᵢ)] = min(dp[···], dp[v] + cᵢ)饮料:(100, 2000)、(2, 50)、(4, 40)、(5, 30)、(3, 20)(格式:花费, 容量)。
买 (2,50)、(4,40)、(3,20):容量 110 ≥ 100,费用 9
买 (2,50)、(4,40)、(5,30):容量 120 ≥ 100,费用 11
买 (3,20)、(4,40)、(5,30):容量 90 < 100 ✗
买 (100,2000):容量 2000 ≥ 100,费用 100
只买 (2,50)、(4,40):容量 90 < 100 ✗
最小费用 9
dp[v] 记录"容量至少 v 的最低花费"
只容量恰好凑够才有值,超过 100 的压到 100
最终 dp[100] = 9(由容量 110 的方案压缩而来)
✅ dp[100] = 9
答案 9 ✓
样例 2 把 L 提到 141;样例 3 则去掉了那瓶"巨无霸"。
| 样例 | L | 可用饮料 | 总容量 | 能否满足 | 答案 |
|---|---|---|---|---|---|
| 2 | 141 | 5 种全有 | 140 + 2000 = 2140 | 能 | 100 |
| 3 | 141 | 只有后 4 种 | 50+40+30+20 = 140 | 不能(140 < 141) | no solution |
若全买后 4 种:容量 140 < 141,不满足 ✗
所以必须买那瓶 (100, 2000)
容量瞬间达到 2000 ≥ 141,费用 100
虽然它单价贵,但"够用"是硬条件
✅ 100
所有饮料容量之和 = 50 + 40 + 30 + 20 = 140
即使全买也只有 140 < 141
所以 dp[141] 永远是 INF
输出 no solution
✅ no solution
dp 初值设为"无穷大",递推结束后看 dp[L] 是否仍为无穷大即可。这与"有解时求出最小值"用同一套代码,非常优雅。dp[v] = 容量达到 v 的最少费用,容量压到 L
dp[费用] = 最大容量,再找最小的费用使容量 ≥ L
| 方案 | 状态数 | 可行性 |
|---|---|---|
| 按容量 DP | ≤ 2001 | ✅ 稳过 |
| 按费用 DP | ≈ 5 × 10⁸ | ❌ 不可行 |
| 按容量/性价比贪心 | — | ❌ 0/1 背包下不保证最优 |
第一行输入 N 和 L,随后 N 行输入每种的售价与容量。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; const long long INF = 4e18; long long dp[2005]; // dp[v]:容量达到 v 的最少费用 int main() { int N, L; scanf("%d %d", &N, &L); for (int v = 0; v <= L; v++) dp[v] = INF; dp[0] = 0; for (int i = 0; i < N; i++) { long long c, l; scanf("%lld %lld", &c, &l); // 0/1 背包:容量维度倒序遍历 for (int v = L; v >= 0; v--) { if (dp[v] == INF) continue; int nv = (int)min((long long)L, (long long)v + l); // 容量压缩 dp[nv] = min(dp[nv], dp[v] + c); } } if (dp[L] == INF) puts("no solution"); else printf("%lld\n", dp[L]); return 0; }
v 要倒序遍历?这是 0/1 背包的标准要求:倒序时 dp[v] 还是"没考虑第 i 件"的旧值,保证每种饮料最多买一瓶。dp[v] 可能已经被本件更新过,就会变成"可以重复购买"(完全背包),与题意不符。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
dp[0] = 0,其余 INF | 初始化 | 容量 0 免费达成,其他暂不可达 |
for (v = L; v >= 0; v--) | 倒序 | 保证 0/1 特性 |
nv = min(L, v + l) | 容量压缩 | 超过 L 一律压到 L |
dp[nv] = min(dp[nv], dp[v] + c) | 转移 | 取最小费用 |
dp[L] == INF | 无解判定 | 从未被更新说明凑不够 |
min(L, …));③ INF 取得太小导致被误判为可达;④ 费用之和超过 int(500 × 10⁶ = 5 × 10⁸ 虽在 int 内,但保险起见用 long long)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 100 | 9 | 题面样例 1 |
5 141 | 100 | 题面样例 2(必须买贵的才够量) |
4 141 | no solution | 题面样例 3(总量不够) |
1 1 | 7 | 只有一瓶,刚好够 |
1 5 | no solution | 容量不够,无解 |
v + l 可能超过 L,要用 min(L, v+l)。dp[L] 仍是 INF 时要输出 no solution。一个长度 L+1 的 dp 数组(L ≤ 2000)。
✅ 约 100 万次操作,瞬间完成。关键在于"用容量当维度、费用当值",这样状态数才够小。
// 0/1 背包求"容量至少 L 的最少费用" // 核心:把"至少"通过容量压缩变成"恰好" for (int v = 0; v <= L; v++) dp[v] = INF; dp[0] = 0; for (每个物品) for (int v = L; v >= 0; v--) { if (dp[v] == INF) continue; int nv = min(L, v + 物品容量); dp[nv] = min(dp[nv], dp[v] + 物品费用); } // 答案 = dp[L](若仍为 INF 则无解) // 背包题选择维度的原则 // 比较"容量范围"和"价值范围",用更小的那个当维度 // 本题:容量 ≤ 2000,费用可达 5×10^8 -> 选容量 // 经典 0/1 背包:容量 ≤ 1e5,价值可达 1e9 -> 也选容量 // "至少"型背包的通用技巧 // 把超过上界的部分全部压到上界,避免数组开大
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 容量压缩 | "至少 L" 转成 "恰好 L" | 所有"达到某阈值即可"的背包 |
| 0/1 倒序 | 保证每件最多用一次 | 所有 0/1 背包 |
| 维度选择 | 用范围小的当维度 | 背包、DP 的状态设计 |
dp[v] 可能已经用过本件,正好实现"重复购买"。倒序 vs 正序,是背包问题最经典的一个记忆点。)