列表中值总和最多为 K 的元素的最大数量

Question

我有一个练习要求：

• 考虑一个具有 n 个正整数和一个整数 k 的向量 T。提出一种算法，从 T 中选择最大数量的元素，使得所选元素的总和小于或等于 k。

我所做的是：

 def findSumCount(L, k):
  L.sort()
  totalSum = L[0]
  count = 1
  for i in range(1, len(L), 1):
    if(totalSum + L[i] <= k):
      count = count + 1
      totalSum = totalSum + L[i]
    if(totalSum + L[i] > k): break

  return count

findSumCount([1, 2, 3, 4], 5)

我认为当我对条目上的数组进行排序时，这是有效的（如果您认为它不起作用，请给我一个反例）。但是，如果我之前没有排序（即在没有事先排序的情况下迭代数组），我就看不到前进的道路。有什么想法吗？

Answer 1

采用总和低于某些

k

的尽可能多的元素意味着您希望始终选择具有最低值的元素。因此，对输入数组进行排序，然后按升序排列元素，直到超过

k

是您能做的最好的事情。复杂度低于 O(n logn + n) ~ O(n logn)，其中 n 是 T 的大小。您为排序付出的成本:)。