此问题是LeetCode 1710（简易）问题的变体。我想知道我的解决方案在时间和空间上的复杂性是什么，以及是否有更好的方法来解决这个问题。
问题：我们想根据卡车可以容纳多少个箱子（由truckSize给定）找到卡车可以容纳的最大产品数量。
变量（带有示例）：
num = 3（产品数）boxes = [1,2,3]（每种产品的盒子数的整数列表）unitSize = 3（仅代表unitPerBox列表的大小）unitsPerBox = [3,2,1]（代表每个包装盒中装箱数量的整数列表）truckSize = 3（卡车可以携带的箱子数量）。因此，在这个例子中，卡车将能最大的持有7 units，因为
Product 0 = 1 box with 3 units -> [3]
Product 1 = 2 boxes with 2 units -> [2] [2]
Product 2 = 3 boxes with 1 unit -> [1] [1] [1]
Since the truck can hold 3 boxes, we would maximize units by adding boxes [3] + [2] + [2] = 7 units.
这是我的代码，我正在使用贪婪的解决方案计算所有可能的盒子。packedList是我使用的列表，其中包含所有产品的所有包装盒的单位。我对其进行归类并归结起来truckSize以得出最终答案。
def getMaxUnit(num, boxes, unitSize, unitsPerBox, truckSize)
packedList = []
maxUnits = 0
for i in range(num):
for j in range(boxes[i]):
packedList.insert(len(packedList), unitsPerBox[i])
packedList.sort(reverse = True)
# Edge case - if truckSize is bigger, then
# we can use every box in packedList
if truckSize > len(packedList):
for i in range(len(packedList)):
maxUnits += packedList[i]
else:
# Since list is sorted, get the max number of units
# from packedList
for i in range(truckSize):
maxUnits += packedList[i]
return(maxUnits)
莱斯说
假设（truckSize< Z），代码的复杂度将为：O(Z log(Z))。您的代码的空间复杂度为：O(Z)。之所以如此复杂是因为您首先对其进行构建packedList和排序。
我认为您可以进一步改善代码的时间和空间复杂度。您可以建立一个元组列表，每个元组将包含<number-of-units, number-of-boxes>。对于您的样本输入，将是这样的：
[(3, 1), (2, 2), (1, 3)]
然后按单位数量的降序对这个列表进行排序（元组的第一项）。由于这个问题要求最大化装载卡车中的单元数。然后，您可以通过选择具有大量单位的框来进行贪婪的选择。以某种方式选择框，使其truckSize不受约束。
元组列表的大小为O(X)。然后排序此列表将花费O(X log(X))。通过这种方式，您可以减少此问题的时间和空间复杂度，这X显然比少Z。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句