题目

请你将一些箱子装在 一辆卡车 上。给你一个二维数组 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

思路

简单的贪心算法，每一次挑选容量最大的卡车，直到挑够给定卡车数量或者挑完所有卡车。

具体做法是将给定的boxTypes数组按照第二个元素从大到小排序，然后遍历这个排序后的数组，从前往后开始累加，直到trucksize=0或者将数组遍历完即可返回。

题解

class Solution:
    def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
      # 排序
        boxtype = sorted(boxTypes, key=lambda x: x[1], reverse=True)
        ans = 0
        # 遍历排序后的数组
        for i in range(len(boxtype)):
          # 如果剩余卡车数量大于遍历到的这一组卡车数量，直接全部加上
            if truckSize > boxtype[i][0]:
                ans += boxtype[i][0] * boxtype[i][1]
                truckSize -= boxtype[i][0]
           # 如果小于，则加上剩余卡车的数量，然后返回结果
            else:
                ans += truckSize * boxtype[i][1]
                return ans
        # 遍历完所有卡车后还有剩余的情况，直接返回
        return ans