列表定义如下:[1, 2, 3]
其子列表如下:
[1], [2], [3],
[1,2]
[1,3]
[2,3]
[1,2,3]
给定k,例如3,任务是找到元素和小于k的子列表的最大长度。
我知道python中的
itertools
,但它会导致较大列表的分段错误。有没有其他有效的算法来实现这一点?任何帮助都将不胜感激。我的代码是允许的:
from itertools import combinations
def maxLength(a, k):
#print a,k
l= []
i = len(a)
while(i>=0):
lst= list(combinations(sorted(a),i))
for j in lst:
#rint list(j)
lst = list(j)
#print sum(lst)
sum1=0
sum1 = sum(lst)
if sum1<=k:
return len(lst)
i=i-1
最佳答案
就我所见(既然你把子数组当作初始数组的任何项目),你可以使用贪婪算法,使用O(N*log(N))
复杂性(你必须对数组排序):
1. Assign entire array to the sub array
2. If sum(sub array) <= k then stop and return sub array
3. Remove maximim item from the sub array
4. goto 2
例子
[1, 2, 3, 5, 10, 25]
k = 12
解决方案
sub array = [1, 2, 3, 5, 10, 25], sum = 46 > 12, remove 25
sub array = [1, 2, 3, 5, 10], sum = 21 > 12, remove 10
sub array = [1, 2, 3, 5], sum = 11 <= 12, stop and return
作为另一种选择,您可以从空的子数组开始,从最小值到最大值相加,而和则小于或等于“cc>”:
sub array = [], sum = 0 <= 12, add 1
sub array = [1], sum = 1 <= 12, add 2
sub array = [1, 2], sum = 3 <= 12, add 3
sub array = [1, 2, 3], sum = 6 <= 12, add 5
sub array = [1, 2, 3, 5], sum = 11 <= 12, add 10
sub array = [1, 2, 3, 5, 10], sum = 21 > 12, stop,
return prior one: [1, 2, 3, 5]
关于python - 总和小于给定总和的最大子集,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/41284951/