卡车上的最大单元数

标签: 贪心 数组 排序

难度: Easy

请你将一些箱子装在 一辆卡车 上。给你一个二维数组 boxTypes ，其中 boxTypes[i] = [numberOfBoxesi, numberOfUnitsPerBoxi] ：

  • numberOfBoxesi 是类型 i 的箱子的数量。
  • numberOfUnitsPerBoxi 是类型 i 每个箱子可以装载的单元数量。

整数 truckSize 表示卡车上可以装载 箱子 的 最大数量 。只要箱子数量不超过 truckSize ，你就可以选择任意箱子装到卡车上。

返回卡车可以装载 单元 的 最大 总数。

 

示例 1：

输入：boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
输出：8
解释：箱子的情况如下：
- 1 个第一类的箱子，里面含 3 个单元。
- 2 个第二类的箱子，每个里面含 2 个单元。
- 3 个第三类的箱子，每个里面含 1 个单元。
可以选择第一类和第二类的所有箱子，以及第三类的一个箱子。
单元总数 = (1 * 3) + (2 * 2) + (1 * 1) = 8

示例 2：

输入：boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
输出：91

 

提示：

  • 1 <= boxTypes.length <= 1000
  • 1 <= numberOfBoxesi, numberOfUnitsPerBoxi <= 1000
  • 1 <= truckSize <= 106

Submission

运行时间: 32 ms

内存: 16.4 MB

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        b = sorted(boxTypes, key = lambda x: -x[1])
        res = 0
        for num, size in b:
            cnt = min(truckSize, num)
            res += cnt * size
            truckSize -= cnt
            if truckSize == 0:
                break
        return res

Explain

此题解采用了贪心算法的思想，首先根据每个箱子能装载的单元数量对箱子进行降序排序。排序后，从单元数最多的箱子开始装载，以此确保每次装载能获得最大的单元数。在装载的过程中，根据当前卡车剩余的容量和每种类型箱子的数量来决定实际能装载的箱子数量，直到卡车装满或者所有箱子类型都尝试过为止。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
        # 对箱子类型按照每个箱子的单元数进行降序排序
        b = sorted(boxTypes, key = lambda x: -x[1])
        res = 0  # 初始化最大单元数为0
        for num, size in b:
            cnt = min(truckSize, num)  # 计算当前类型箱子能装载的最大数量
            res += cnt * size  # 更新已装载的单元数
            truckSize -= cnt  # 更新卡车剩余容量
            if truckSize == 0:
                break  # 如果卡车已满，提前结束循环
        return res

Explore

选择按照每个箱子的单元数进行降序排序是因为这样可以优先装载单元数最多的箱子，从而在卡车容量有限的情况下尽可能多地装载单元。这种方法基于贪心算法的思想，即在每一步都选择当前看来最优的选择。在这个问题中，优先装载单元数多的箱子能够保证在卡车容量固定且每次选择都是独立的情况下得到最多的总单元数。因此，这种排序方式在本题的条件下总是能保证得到最大的总单元数。

算法的实现考虑到了卡车未装满的情况。在每次循环中，算法先计算当前类型的箱子能装载的最大数量（取卡车剩余容量和该类型箱子总数的最小值），并相应地更新装载的单元数和卡车的剩余容量。如果所有箱子的数量总和小于卡车的容量，循环会在尝试完所有箱子类型后自然结束，此时已装载的单元数即为所有箱子能提供的最大单元数。因此，算法能正确处理卡车未装满的情况。

在贪心算法的框架下，每种箱子的装载数量是通过计算卡车当前剩余容量和该类型箱子的可用数量的最小值来决定的。这保证了每一步都是在当前情况下可能的最大装载量，即在每次选择中都尽可能多地装载单元数最多的箱子。这种局部最优的选择策略在整体上导致了全局最优解，即总单元数的最大化。

在Python中，使用`sorted`函数时，`lambda x: -x[1]`作为排序关键字（key function）可以将元素按照元组中第二个元素的负值排序。因为对数字取负会将原有的顺序反转，所以这种方式实际上是将第二个元素（即每个箱子的单元数）按从大到小的顺序排列，从而实现降序排序。