GESP 题解库 / 6 级题解 / [GESP202309 六级] 小杨买饮料 · 第 22 / 27 题
GESP202309 六级 · B3873 · 中等

小杨买饮料

每种饮料至多买一瓶,使总容量 ≥ L 且花费最少。

📊
N ≤ 500, L ≤ 2000
数据规模
🔢
long long
费用范围
⚡
O(NL)
时间复杂度
🎯
0/1 背包(最小费用)
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

商店有 N 种饮料,第 i 种售价 cᵢ、容量 lᵢ。要求:每种至多买 1 瓶;总容量 ≥ L;在此前提下花费最少。若无论如何都满足不了容量要求,输出 no solution。

💡
人话翻译:标准的"0/1 背包求最小费用"。
设 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 且费用最小

需要解决的问题

02
思维导图
整理解题思路的全貌
🥤 dp[容量] = 最少费用
🧠 状态
dp[v]:容量恰好 v 的最少费用
v 只取 0 ~ L
超过 L 的都压到 L
答案 = dp[L]
🔁 转移
对每种饮料 (c, l)
v 从 L 递减到 0(0/1 背包)
dp[min(L, v+l)] = min(…, dp[v] + c)
取 min
🚫 无解判定
初始化 dp[0] = 0,其余为 INF
跑完若 dp[L] 仍为 INF
说明凑不到 L 容量
输出 no solution
⚠️ 易错点
正序遍历 v(会重复购买)
忘记容量压缩导致越界
INF 设太小
费用和可能超 int
03
样例手算推导
三个样例的完整推演

🧮 样例 1:N = 5,L = 100

饮料:(100, 2000)、(2, 50)、(4, 40)、(5, 30)、(3, 20)(格式:花费, 容量)。

1
候选方案对比

买 (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

2
DP 视角

dp[v] 记录"容量至少 v 的最低花费"

只容量恰好凑够才有值,超过 100 的压到 100

最终 dp[100] = 9(由容量 110 的方案压缩而来)

✅ dp[100] = 9

答案 9 ✓

🔑
注意"容量压缩"的作用:方案的总容量是 110,但我们并不需要区分 110、120、2000——它们都"够用"。所以把它们统一记为到达 L = 100,dp 数组就只需要 101 个位置。

🧮 样例 2 与样例 3:无解是怎么出现的

样例 2 把 L 提到 141;样例 3 则去掉了那瓶"巨无霸"。

样例L可用饮料总容量能否满足答案
21415 种全有140 + 2000 = 2140能100
3141只有后 4 种50+40+30+20 = 140不能(140 < 141)no solution
1
样例 2 的取舍

若全买后 4 种:容量 140 < 141,不满足 ✗

所以必须买那瓶 (100, 2000)

容量瞬间达到 2000 ≥ 141,费用 100

虽然它单价贵,但"够用"是硬条件

✅ 100

2
样例 3 为什么无解

所有饮料容量之和 = 50 + 40 + 30 + 20 = 140

即使全买也只有 140 < 141

所以 dp[141] 永远是 INF

输出 no solution

✅ no solution

⚠️
无解的判定很简单:如果所有饮料的容量之和都小于 L,那就一定无解(全买都不够)。
实现时不必特判——只要把 dp 初值设为"无穷大",递推结束后看 dp[L] 是否仍为无穷大即可。这与"有解时求出最小值"用同一套代码,非常优雅。
04
解法对比
按容量 DP vs 按费用 DP / 贪心

⚔️ 解法对比

🟢 按容量做 0/1 背包(推荐) 推荐

dp[v] = 容量达到 v 的最少费用,容量压到 L

  • 时间 O(NL) = 10⁶
  • N = 500、L = 2000 时轻松通过
  • 代码 20 行
  • 空间 O(L)
💡
维度选择依据:容量维度只有 2001 个状态,而费用维度可达 5 × 10⁸——所以必须把"容量"当维度、把"费用"当值。

🟠 按费用做背包

dp[费用] = 最大容量,再找最小的费用使容量 ≥ L

  • 费用上限 500 × 10⁶ = 5 × 10⁸
  • 数组开不下
  • 时间也不可能
  • 完全不可行
⚠️
量级对比:容量 2000 vs 费用 5 × 10⁸——差了 25 万倍。背包题永远选"范围更小"的那个当维度。

📈 性能对比

方案状态数可行性
按容量 DP≤ 2001✅ 稳过
按费用 DP≈ 5 × 10⁸❌ 不可行
按容量/性价比贪心—❌ 0/1 背包下不保证最优
05
算法流程图
0/1 背包求最小费用
开始读入 N、L 和每种的 (cᵢ, lᵢ)dp[0] = 0,dp[1..L] = 无穷大逐种处理饮料 iv 从 L 递减到 0(保证 0/1 特性)dp[v] 是否可达(不是无穷大)?是 ✓dp[min(L, v+l)] = min(…, dp[v] + c)否 ✗跳过全部处理后检查 dp[L]dp[L] 仍为无穷大则输出 no solution,否则输出 dp[L]处理下一种饮料
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🥤 最少花费计算器

第一行输入 N 和 L,随后 N 行输入每种的售价与容量。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

#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)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

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

输入答案考察点
5 100
100 2000 / 2 50 / 4 40 / 5 30 / 3 20
9题面样例 1
5 141
100 2000 / 2 50 / 4 40 / 5 30 / 3 20
100题面样例 2(必须买贵的才够量)
4 141
2 50 / 4 40 / 5 30 / 3 20
no solution题面样例 3(总量不够)
1 1
7 1
7只有一瓶,刚好够
1 5
1 1
no solution容量不够,无解
✅
自查清单:① 倒序遍历吗?② 压缩容量了吗?③ 判无解了吗?

🚨 易错点清单

⚠️
正序遍历:会退化成"可以重复买",必须倒序。
⚠️
忘记压缩容量:v + l 可能超过 L,要用 min(L, v+l)。
⚠️
无解判定漏掉:dp[L] 仍是 INF 时要输出 no solution。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(NL)
空间复杂度
O(L)
N, L 最大
500 × 2000
运算量
约 10⁶

时间怎么算的?

空间都用在哪?

一个长度 L+1 的 dp 数组(L ≤ 2000)。

✅ 约 100 万次操作,瞬间完成。关键在于"用容量当维度、费用当值",这样状态数才够小。

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

🔗 常用技巧小抄

// 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 正序,是背包问题最经典的一个记忆点。)