和小于给定和的最大子集
和小于给定和的最大子集
提问于 2016-12-22 22:03:35
列表的定义如下：[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回答 2
Stack Overflow用户
发布于 2016-12-22 22:14:54
看，生成幂集合需要O(2^n)时间。这是相当糟糕的。您可以改用动态编程方法。
在这里查看算法。http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
是的，https://www.youtube.com/watch?v=s6FhG--P7z0 (图沙尔很好地解释了一切) :D
Stack Overflow用户
发布于 2020-02-16 06:33:31
假设一切都是积极的。(处理负片是这方面的一个简单扩展，留给读者作为练习)。对于所描述的问题，存在O(n)算法。使用O(n)中值选择，我们根据中值对阵列进行分区。我们求出左边的和。如果它大于k，那么我们不能取所有的元素，因此我们必须在左半部分尝试取较小的集合。否则，我们从k中减去左半部分的和，然后在右半部分上递归，看看我们还可以接受多少个元素。
基于中值select对阵列进行分区并仅在一半的1上重复产生n+n/2 +n/4 +n/8的运行时间。几何总和为O(n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41284951
复制相关文章
相似问题