列表定义如下：[1, 2, 3]
其子列表是：
[1], [2], [3],
[1,2]
[1,3]
[2,3]
[1,2,3]
对于示例 3，给定 K，任务是找到元素总和小于等于 k 的子列表的最大长度。
我知道itertools在 python 中，但它会导致较大列表的分段错误。有没有其他有效的算法来实现这一点？任何帮助，将不胜感激。
我的代码是允许的：
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
您可以使用动态规划解决方案 http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/@Apy 链接到的。这是一个 Python 示例：
def largest_subset(items, k):
res = 0
# We can form subset with value 0 from empty set,
# items[0], items[0...1], items[0...2]
arr = [[True] * (len(items) + 1)]
for i in range(1, k + 1):
# Subset with value i can't be formed from empty set
cur = [False] * (len(items) + 1)
for j, val in enumerate(items, 1):
# cur[j] is True if we can form a set with value of i from
# items[0...j-1]
# There are two possibilities
# - Set can be formed already without even considering item[j-1]
# - There is a subset with value i - val formed from items[0...j-2]
cur[j] = cur[j-1] or ((i >= val) and arr[i-val][j-1])
if cur[-1]:
# If subset with value of i can be formed store
# it as current result
res = i
arr.append(cur)
return res
ITEMS = [5, 4, 1]
for i in range(sum(ITEMS) + 1):
print('{} -> {}'.format(i, largest_subset(ITEMS, i)))
Output:
0 -> 0
1 -> 1
2 -> 1
3 -> 1
4 -> 4
5 -> 5
6 -> 6
7 -> 6
8 -> 6
9 -> 9
10 -> 10
在上面arr[i][j] is True如果设置值为i可以选择items[0...j-1]。自然arr[0]仅包含True可以选择空集以来的值。同样，对于所有连续行，第一个单元格是False因为不能有非零值的空集。
对于其余单元格，有两种选择：
- 如果已经存在一个值为
i即使不考虑item[j-1]值为True
- 如果存在一个值为
i - items[j - 1]然后我们可以向其中添加项目并获得一个值为i.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
