python - 总和小于给定总和的最大子集

列表定义如下：[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/