小杨买饮料 题解

题目分析

小杨要从 (N) 种饮料中选购，每种饮料有价格 (c_i) 和容量 (l_i)，且每种最多买一瓶。他希望总容量至少达到 (L) 的前提下，花费的总价格尽可能小。如果无论如何组合都无法让总容量达到 (L)，则输出 no solution。

这本质上是一个0-1背包问题的变形：通常的背包问题是“在总重量不超过 (W) 的条件下最大化价值”，而本题是“在总容量不低于 (L) 的条件下最小化价格”。我们可以用动态规划来解决。

解题思路

状态定义

设 dp[j] 表示获得总容量至少为 (j) 时所需要的最小花费，其中 (0 \le j \le L)。

为什么上界只到 (L)？因为一旦容量超过 (L)，我们只关心“已经满足要求”这一事实，多出来的容量并不会带来额外收益，所以可以将所有超过 (L) 的容量视为 (L) 来处理。这样可以大大缩小状态空间。

转移方程

我们依次考虑每一种饮料（类似0-1背包中逐个考虑物品）。对于当前饮料，价格为 (c)，容量为 (l)，它可以选择买或不买。如果选择购买，那么在新状态中，原来的容量 (j) 会变成 (\max(j - l, 0)) 加上 (l) 后的值，等价于向“至少”的目标贡献了 (l) 的容量。写成转移式为：

[
dp[j] = \min(dp[j],\ dp[\max(j - l, 0)] + c)
]

注意容量是“至少”的条件，因此购买后新的容量至少为 (j)，这可以由原先容量至少为 (\max(j - l, 0)) 的状态转移而来（即原状态还差 (l) 就能达到 (j)，或者原状态已经超过 (j-l) 甚至已经达到 (L)）。

初始化

• (dp[0] = 0)：要获得至少 0 毫升，花费为 0。
• 对于 (j = 1) 到 (L)，(dp[j] = \infty)（程序中用一个非常大的数表示暂时无法达到）。

最终答案就是 (dp[L])。如果 (dp[L]) 仍为 (\infty)，说明无法满足要求，输出 no solution。

算法说明

本题使用一维动态规划来节省空间，与0-1背包的滚动数组优化完全一致。具体步骤如下：

1. 读入 (N, L)，初始化 cost 数组长度为 (L+1)，cost[0] = 0，其余为极大值 INF。
2. 循环读入每种饮料的 (c) 和 (l)。
3. 对于每种饮料，从 (j = L) 向下遍历到 (0)，进行状态转移：

   cpp
   复制
   1cost[j] = min(cost[j], cost[max(j - l, 0)] + c);

   逆序遍历的原因是每种饮料只能使用一次，保证当前物品不会在同一次决策中被重复使用。
4. 处理完所有饮料后，如果 cost[L] == INF，输出 no solution；否则输出 cost[L]。

容量截断的解释

max(j - l, 0) 的作用是将“超过 L 的容量”统一截断为 L。比如 (L=100)，我们已经有了 120 毫升（被等价记录在 dp[100] 中），再买一瓶 30 毫升的饮料，实际容量变成 150 毫升，但我们只关心它仍然满足至少 100 毫升，因此依然落在 dp[100] 的状态里。这个操作保证了数组大小只需 (O(L))，也保证了转移的正确性。

时间复杂度分析

• 外层循环遍历 (N) 种饮料，每次需要更新 (O(L)) 个状态。
• 总时间复杂度为 (O(N \times L))。
• 空间复杂度为 (O(L))。

本题 (N \le 500)，(L \le 2000)，运算量约为 (10^6) 级别，可以轻松通过所有测试点。

参考代码

cpp
复制
1#include <iostream>
2using namespace std;
3
4const int INF = 1000000000;   // 一个足够大的数表示无穷大
5int cost[2001];               // dp数组，0..L
6
7int main() {
8    int N = 0, L = 0;
9    cin >> N >> L;
10    cost[0] = 0;
11    for (int i = 1; i <= L; i++)
12        cost[i] = INF;        // 初始化
13
14    for (int i = 0; i < N; i++) {
15        int c = 0, l = 0;
16        cin >> c >> l;
17        // 0-1背包逆序更新
18        for (int j = L; j >= 0; j--)
19            cost[j] = min(cost[j], cost[max(j - l, 0)] + c);
20    }
21
22    if (cost[L] == INF)
23        cout << "no solution" << endl;
24    else
25        cout << cost[L] << endl;
26
27    return 0;
28}

代码解释

• INF 设为 (10^9)，大于可能的最大花费（所有 (c_i) 相加最多为 (500 \times 10^6 = 5\times 10^8)），确保不会被误认为是有效解。
• cost 数组大小为 2001，略大于 (L) 的最大值 2000，安全起见直接声明了最大可能长度。
• 初始化 cost[0] = 0 表示起点，其余为 INF 表示不可达。
• 对每种饮料读入 c 和 l 后，利用 for (int j = L; j >= 0; j--) 的逆序循环，确保每个物品至多被选一次。
• max(j - l, 0) 实现了“容量至少为 j”的截断逻辑，状态转移到 cost[max(j - l, 0)] + c。
• 最后判断 cost[L] 即可得出最少花费或输出 no solution。

总结

本题是0-1背包的简单变形，关键在于将“总容量至少为 L”通过截断处理转化为与普通背包相似的状态设计，并使用一维逆序更新求解。希望同学们通过本题能够更加熟悉动态规划中状态定义的灵活性以及边界条件的处理方式。