1. 什么是最优装载问题？
最优装载问题是贪心算法里的经典问题。
问题可以描述为：
有一艘船，最大载重量为 。现在有 个物品，每个物品都有自己的重量。要求在不超过船最大载重量的前提下，装入尽可能多的物品。
注意，这里的目标通常是：
装入的物品数量最多，而不是让总重量最大。
生活映射假设你手里有一笔固定预算
coins，面前有很多雪糕，每根雪糕的价格为costs[i]。每根雪糕带来的收益都一样，都是“买到 1 根”，因此目标就是在不超过预算的前提下，买到尽可能多的雪糕。这和最优装载问题是同一种思路：预算
coins相当于船的容量，雪糕价格相当于物品重量，目标都是让选中的数量尽可能多。
2. 举个例子
假设船的最大载重量是：
有这些物品：
如果想装尽可能多的物品，应该优先装轻的。
先排序：
然后从小到大装：
刚好装满，可以装 个物品。
如果一开始装了 ，剩余容量只有 ，最多只能再装一个 或 ，装入的数量就变少了。
3. 贪心思路
最优装载问题的贪心策略是：
每次优先选择重量最小的物品。
原因很直观：物品越轻，占用容量越少，留下的剩余容量越多，就越容易继续装更多物品。
算法步骤：
- 将所有物品按照重量从小到大排序；
- 依次尝试装入物品；
- 如果当前总重量加上这个物品不超过容量 ，就装入；
- 如果超过容量，就直接停止。由于数组已经升序排序，当前物品装不下，后续更重的物品也必然装不下。
4. 为什么这个贪心是对的？
4.1 直观替换解释
假设我们想装最多数量的物品。如果某个方案中装了一个较重的物品，却没有装一个更轻的物品，那么可以把较重物品换成这个更轻的物品。
这样做之后：
- 装入的物品数量不变；
- 总重量只会减少，不会增加；
- 剩余容量只会变多，不会变少。
因此，优先选择轻的物品一定不会吃亏。
4.2 补充：反证法证明
假定贪心思路取得的序列为 （长度为 ，代表前 个最便宜/最轻的物品），真实最优解取得的序列为 （长度为 ）。
由最优解的定义，其装入数量不小于任何可行解，因此有 。我们只需要证明 成立，即可得证 。
利用反证法证明 ，假设 ：
根据贪心决策，我们总是优先选择排序数组中当前最小的可用物品，因此选择的 在排序好的数组里必然是一段连续的前缀 。并且因为装不下第 个物品，所以有：
而最优解选择的方案在已排序数组中分布可能是不连续的，如下图所示：
利用“将最优解中分布靠后的物品，替换为排序数组中未被选择且靠前的较轻物品，总费用不会增加，同时数量不变”的特性，我们也可以将真实最优解调整为某段连续的前缀：
调整后最优解的前缀即为 ，由于它是可行解，其总成本不超过容量 ：
又因为假设了 ，可以推出 ，进而有：
这与贪心结论中的 产生矛盾。
因此假设不成立，必然有 。结合 可得 。贪心解必然能够取得与最优解相同的长度。
5. Java 实现
对应到本题，costs[i] 就是每根雪糕的价格，coins 就是手里的钱。
import java.util.Arrays;
class Solution { public int maxIceCream(int[] costs, int coins) { // 先按价格从低到高排序，优先买便宜的雪糕 Arrays.sort(costs);
int ans = 0; for (int cost : costs) { // 当前雪糕买得起，就买下，并扣除对应费用 if (coins >= cost) { ans++; coins -= cost; } else { // 当前价格已经买不起，后面更贵的也买不起 break; } }
return ans; }}6. 复杂度分析
- 时间复杂度：排序需要 ，遍历数组需要 。总时间复杂度为 。
- 空间复杂度：，主要取决于排序所需要的栈空间。
7. 计数排序优化解法（线性时间）
由于题目提示中给出了价格上限 ，数值范围较小。我们还可以使用计数排序将排序的时间复杂度优化至线性，从而在海量数据时效率更高。
class Solution { public int maxIceCream(int[] costs, int coins) { int max = 0; // 找到最大价格，用来确定计数数组的长度 for (int cost : costs) { max = Math.max(max, cost); }
int[] freq = new int[max + 1]; // freq[i] 表示价格为 i 的雪糕有多少根 for (int cost : costs) { freq[cost]++; }
int ans = 0; // 按价格从低到高尝试购买 for (int i = 1; i <= max; i++) { if (freq[i] > 0) { if (coins >= i) { // 贪心一次性购买当前价格下能买得起的所有雪糕 int buy = Math.min(freq[i], coins / i); ans += buy; coins -= buy * i; // 如果当前价格没能全买下，说明钱已花光，后续更贵的更买不起 if (buy < freq[i]) { break; } } else { break; } } } return ans; }}- 时间复杂度：，其中 为最大雪糕价格（）。
- 空间复杂度：，需要一个长度为 的计数数组。
8. 和 0-1 背包问题的区别
最优装载问题很容易和普通的背包问题混淆。
8.1 最优装载问题
- 目标：在容量限制内，装入尽可能多数量的物品。
- 特点：只关心物品的重量和数量，不关心物品的价值（或者可以看作所有物品的价值恒定为 ）。
- 策略：优先装最轻的。
8.2 0-1 背包问题
- 目标：在容量限制内，让装入物品的总价值最大。
- 特点：每个物品除了重量，还有不同的价值，不能简单地按重量、价值或性价比贪心。
- 策略：通常需要使用动态规划。
8.3 拓展思考：价值不恒定为 1 时能否贪心？
如果每个物品对答案的贡献不恒定为 ，而是多给一个数组 values。每件物品费用为 costs[i]，价值为 values[i]，求解花费不超过 coins 的最大价值。
答案是：不可以。
平时学习的「01 背包」无法使用简单的贪心算法来解决。以下是反例分析：
假设容量限制为 。有三件物品：
- 物品 A：
cost = 6, value = 7（性价比约为 ） - 物品 B：
cost = 5, value = 5（性价比为 ） - 物品 C：
cost = 5, value = 5（性价比为 ）
如果采用贪心策略，优先选择性价比最高的 A，背包容量剩余 ，无法再装入 B 和 C，最终获得的总价值为 。 而最优解是选择 B 和 C，刚好装满背包，获得的总价值为 。
9. 一句话总结
最优装载问题的核心是：
在容量有限的情况下，为了装入最多数量的物品，应该优先装重量最小的物品。
实现口令是：
先排序，再从小到大累加，能装就装，装不下就停。如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时