我有一个练习要求:
- 考虑一个具有 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)
我认为当我对条目上的数组进行排序时,这是有效的(如果您认为它不起作用,请给我一个反例)。但是,如果我之前没有排序(即在没有事先排序的情况下迭代数组),我就看不到前进的道路。有任何想法吗?