卡车上的最大单元数如何用贪心求解？为什么优先装单位价值最高的箱子？

简化版

卡车上的最大单元数按每箱单元数从大到小排序，优先装单位价值最高的箱子。每种箱子能装多少装多少，直到卡车容量用完。

详细版

每个箱子占用的容量都是 1，但不同类型箱子的收益不同，所以优先选择 unitsPerBox 更大的类型一定不亏。排序后遍历箱子类型，当前类型可装数量是 min(boxCount, truckSize)，收益增加 take * unitsPerBox，容量减少 take。

时间复杂度 O(n log n)，空间复杂度取决于排序。若 unitsPerBox 范围很小，也可以用计数桶优化。

完整版教学

一、为什么这是最直接的单位价值贪心

每个箱子都占据卡车 1 个位置，区别只在每箱能带多少单元。既然成本相同，收益越高的箱子越应该先装。

类型 A：每箱 5 单元，占 1 格
类型 B：每箱 2 单元，占 1 格

在容量有限时，用 A 替换 B 会让总收益增加 3，且不增加容量成本。

二、排序依据是什么

排序按照 unitsPerBox 降序，而不是按照箱子数量降序。箱子数量多不代表优先级高，因为卡车容量稀缺，应该先看每个位置能产生多少价值。

排序方式	是否合理	原因
按每箱单元数降序	合理	单位容量收益最大
按箱子数量降序	不合理	数量多但可能收益低
按总单元数降序	不稳定	可能占用太多容量

记忆钩子：容量成本一样时，看单位收益；容量成本不同才看性价比。

这题所有箱子成本都是 1，所以不需要复杂背包。

三、贪心正确性怎么解释

假设某个方案里装了一个低单元箱子 b，但还有一个高单元箱子 a 没装，并且 a.units > b.units。把 b 换成 a，容量不变，总单元数增加。

换前：... + b
换后：... + a
收益提升：a.units - b.units > 0

因此任何最优方案都不应该在能装高收益箱子时优先装低收益箱子。这就是交换论证。

四、用数字例子推演

boxTypes=[[1,3],[2,2],[3,1]]，truckSize=4。

排序后：

[1,3] -> 每箱 3
[2,2] -> 每箱 2
[3,1] -> 每箱 1

装载：

装 1 箱每箱 3：收益 3，剩余容量 3
装 2 箱每箱 2：收益 4，剩余容量 1
装 1 箱每箱 1：收益 1，剩余容量 0
总收益 8

这一步一步都在把当前容量给最值钱的箱子。

五、代码模板

int maximumUnits(int[][] boxTypes, int truckSize) {
    Arrays.sort(boxTypes, (a, b) -> b[1] - a[1]);
    int ans = 0;
    for (int[] box : boxTypes) {
        int take = Math.min(box[0], truckSize);
        ans += take * box[1];
        truckSize -= take;
        if (truckSize == 0) break;
    }
    return ans;
}

注意 box[0] 是箱子数量，box[1] 是每箱单元数。变量名写清楚可以减少数组下标写反的概率。

六、和 0-1 背包有什么区别

0-1 背包里每个物品重量和价值都可能不同，单位价值最高不一定全局最优。但这题每个箱子的容量成本都是 1，而且同类型箱子可以拿多个，本质是把固定容量分给收益最高的单位。

问题	能否简单按单位收益贪心
本题每箱成本相同	可以
普通 0-1 背包	不一定
分数背包	可以

面试时能讲清这个边界，说明不是见到“装东西”就乱套背包。

七、常见误区与追问

误区：按箱子数量排序。 数量多不代表每个容量格收益高。
误区：把 truckSize 当成总重量。 本题每箱占 1 个容量，容量就是箱子数。
误区：装完一种类型后忘记减少容量。 会导致超装。
追问：为什么贪心正确？ 低收益箱子可以被高收益箱子替换，容量不变、收益增加。
追问：能否用桶排序？ 如果每箱单元数范围小，可以按单元数建桶优化排序。
追问：和背包区别是什么？ 成本完全相同，所以单位收益排序足够。

八、加强记忆

卡车装箱记住“每个箱子占一格”。既然成本一样，谁每箱单元数高，谁就优先上车。排序后能装多少装多少，容量用完停止。它像背包但比背包简单，原因就在成本统一，交换论证能直接证明贪心正确。

简化版

详细版