Milk Pails

题目链接（USACO 2016 February Contest, Bronze Problem 1）

题目描述

给定 X、Y、M，求 aX + bY 不超过 M 的最大值，其中 a, b 为非负整数。

数据范围：

• 1 <= X, Y <= 100
• 1 <= M <= 1000

示例

输入：

17 25 77

输出：

76

解释： 取 a = 3, b = 1，3 × 17 + 1 × 25 = 76，不超过 77 且最大。

核心思路

在约束 aX + bY <= M 下，最大化 aX + bY。

Bronze 数据范围很小，直接暴力枚举即可。两种思路：

1. 双重循环：枚举 a 和 b 的所有合法组合，取不超过 M 的最大值；
2. 单层枚举 + 贪心：固定 a，为了让 aX + bY 尽量接近 M，b 直接取 (M - aX) // Y，只需枚举 a。

---

方法一：单层枚举（推荐）

思路及解法

固定 a 后，aX 是常数，要让 aX + bY <= M 且最大，b 当然要尽可能大：

$$b = \left\lfloor \frac{M - aX}{Y} \right\rfloor$$

枚举所有满足 aX <= M 的 a，对每个 a 直接计算最优 b，取最大值即可。

为什么正确：对于固定的 a，b 取上式的值能让 aX + bY 最接近 M 且不超过，是该 a 下的最优解。枚举所有 a，全局最优一定在其中。

代码

def solve():
    x, y, m = map(int, input().split())
    ans = 0
    for a in range(m // x + 1):
        remain = m - a * x
        b = remain // y
        ans = max(ans, a * x + b * y)
    print(ans)

if __name__ == "__main__":
    solve()

复杂度分析

• 时间复杂度：$O(M / X)$，最坏 $O(M)$。
• 空间复杂度：$O(1)$。

---

方法二：双重循环（Bronze 原版）

思路及解法

直接枚举 a 和 b 的所有合法组合：

• a 的范围：0 <= a <= M // X；
• b 的范围：0 <= b <= M // Y；
• 对每组 (a, b)，计算 aX + bY，若不超过 M，更新答案。

代码

def solve():
    x, y, m = map(int, input().split())
    ans = 0
    for a in range(m // x + 1):
        for b in range(m // y + 1):
            total = a * x + b * y
            if total <= m:
                ans = max(ans, total)
    print(ans)

if __name__ == "__main__":
    solve()

复杂度分析

• 时间复杂度：$O((M/X) \times (M/Y))$，Bronze 数据下约 $10^6$，可以通过。
• 空间复杂度：$O(1)$。

---

方法三：数学写法（最小浪费）

思路及解法

换个角度：用 a 个 X 之后，剩余的容量 M - aX 无法被 Y 填满的部分是：

$$\text{waste}(a) = (M - aX) \bmod Y$$

我们要让浪费尽可能小，即：

$$\text{ans} = M - \min_{a} \text{waste}(a)$$

本质上和方法一相同，只是用「最小浪费」的角度表达。

代码

x, y, m = map(int, input().split())
waste = m
for a in range(m // x + 1):
	waste = min(waste, (m - a * x) % y)
print(m - waste)

复杂度分析

• 时间复杂度：$O(M / X)$。
• 空间复杂度：$O(1)$。

---

三种方法对比

方法	时间	空间	特点
单层枚举	$O(M/X)$	$O(1)$	代码短，效率高，推荐
双重循环	$O((M/X)(M/Y))$	$O(1)$	最直观，Bronze 够用
最小浪费	$O(M/X)$	$O(1)$	数学视角，与方法一等价

推荐：Bronze 直接写方法一即可；如果 M 更大，方法一依然高效。

---

力扣上的关联题目

1. LC 365. 水壶问题（场景最接近）

365. 水壶问题 同样是两个水壶 / 容量，但目标不同：

	Milk Pails	LC 365 水壶问题
目标	aX + bY <= M 的最大值	是否存在 aX + bY == target
约束	不超过 M	恰好等于 target
解法	枚举	数论：target 是 gcd(X, Y) 的倍数且 <= X + Y

2. 完全背包类问题（本质相通）

本题可以看作完全背包的「最大价值」版本：

• 两种物品体积分别为 X、Y；
• 价值等于体积；
• 每个物品可以取无限次；
• 总容量 M 内求最大价值。

力扣上完全背包的经典题：

题号	题目	与本题的关系
322	零钱兑换	完全背包，求最少硬币数凑出 amount
279	完全平方数	完全背包，物品是 1, 4, 9, ...
518	零钱兑换 II	完全背包，求方案数
1449	数位成本和为目标值的最大数字	完全背包，求最大价值（与本题最接近）

其中 LC 1449 和本题的「完全背包求最大价值」结构最像，只是它要求恰好等于 target，而本题允许不超过 M。

3. 如果改成完全背包写法

用 dp[j] 表示「容量为 j 时能获得的最大价值」：

def max_value(x, y, m):
    dp = [0] * (m + 1)
    for j in range(1, m + 1):
        if j >= x:
            dp[j] = max(dp[j], dp[j - x] + x)
        if j >= y:
            dp[j] = max(dp[j], dp[j - y] + y)
    return dp[m]

但对于本题 M <= 1000 的规模，枚举法更简单、更直接，完全背包反而是「杀鸡用牛刀」。

---

关联题目总结

问题	力扣对应	核心区别
aX + bY <= M 的最大值	无完全一致原题	本题
aX + bY == target 是否可行	LC 365	恰好等于 vs 不超过
完全背包求最大价值	LC 1449	恰好等于 vs 不超过
完全背包求最少数量	LC 322 / 279	最少 vs 最大
完全背包求方案数	LC 518	方案数 vs 最大值

结论：

• 力扣上没有和本题完全相同的题；
• LC 365（水壶问题） 场景最接近；
• LC 1449（完全背包求最大价值） 背包结构最接近；
• 本题 Bronze 数据小，Python 直接用单层枚举即可，$O(M/X)$ 足够快。

---

关键细节

1. 文件输入输出（USACO 原题）

USACO 原题要求从 pails.in 读入、输出到 pails.out，C++ 代码里需要：

freopen("pails.in", "r", stdin);
freopen("pails.out", "w", stdout);

本地调试或转成 Python 时，直接用标准输入输出即可。

2. 枚举范围

a 的上界是 M // X，超过这个范围 aX 就已经大于 M，不可能满足条件。

3. 为什么方法一里 b 取 (M - aX) // Y 就是最优

固定 a 后，aX 是常数。要让 aX + bY <= M 且最大，bY 应尽量接近 M - aX 但不超过，即 b = floor((M - aX) / Y)。

4. 答案初始值

ans = 0 对应 a = 0, b = 0，合法且一定不超过 M。

总结

• 本质：在约束 aX + bY <= M 下最大化 aX + bY；
• Bronze 做法：双重循环枚举 a、b，$O((M/X)(M/Y))$；
• 优化：固定 a，b 直接取 (M - aX) // Y，$O(M/X)$；
• 力扣关联：LC 365（场景最接近）、LC 1449（背包结构最接近）；
• 通用套路：「两种物品凑不超过 M 的最大值」→ 枚举一种，另一种贪心取最大。

相关题目

• LC 365. 水壶问题（恰好等于 target）
• LC 322. 零钱兑换（完全背包求最少数量）
• LC 279. 完全平方数（完全背包）
• LC 518. 零钱兑换 II（完全背包求方案数）
• LC 1449. 数位成本和为目标值的最大数字（完全背包求最大价值）