如果我可以从数字列表中创建给定数字的总和，请进行递归检查
如果我可以从数字列表中创建给定数字的总和，请进行递归检查
提问于 2018-12-06 02:08:29
我得到了一个号码和一份名单。我必须找到列表中的最大数字数，才能得到给定数字的总和。
def calc_max_baggage (weights, W):
if W==0: # if W == 0 or weights == []: is the same.
return 0
elif weights==[]:
return 0
elif sum(weights)==W:
return len(weights)
elif weights[-1]==W:
return 1
elif W==0:
return 1
option1 = 0+calc_max_baggage(weights[:-1], W)
option2 = 0+calc_max_baggage(weights[1:], W)
return max(option2,option1)
print calc_max_baggage([3,1,2,3,2,1],6)预期输出:4 --最大为1+2+2+1
实际输出:3
回答 2
Stack Overflow用户
发布于 2018-12-06 02:27:03
您可以通过递归地尝试列表中不同的元素组合来解决这个问题(动态编程)。就像这样。
def calc_max_baggage(li, tot, current_bagage=0, max_baggage=0):
if tot == 0 or len(li)==0: return current_bagage
if tot < 0: return 0
for i in range(len(li)):
temp = calc_max_baggage(li[:i] + li[i+1:], tot-li[i], current_bagage+1)
if temp > max_baggage:
max_baggage = temp
return max_baggageStack Overflow用户
发布于 2018-12-06 04:48:45
这是你问题的答案。请问其他人解释为什么它是有效的，因为我理解它只是为了让它适用于您的答案：
from itertools import chain, combinations
weights = (3, 1, 2, 3, 2, 1)
W = 6
# weights = (3, 1, 2, 3, 2, 1) / w = 6 / Output: 4
# weights = [1, 1, 1] / w = 2 / Output: 2
# weights = (1, 1, 1) / w = 7 / Output: 3
# weights = [4,2,1,3] / w = 5 / Output: 2
# weights = [5] / w =5 / Output: 1
def powerset(iterable):
"""
:param iterable: the iterable you want to find all combinations for
:return: each combination of the iterables in this example:
:example:
weights = (3, 1, 2, 3, 2, 1)
w = len(weights)
powersets = []
for x in powerset(weights):
if sum(x) == w:
print(x)
powersets.append(len(x))
Output >>>
(3, 3)
(3, 1, 2)
(3, 1, 2)
(3, 2, 1)
(3, 2, 1)
(1, 2, 3)
(1, 3, 2)
(2, 3, 1)
(3, 2, 1)
(1, 2, 2, 1)
4
"""
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
def calc_max_baggage(weights, W):
powersets = []
# for x in powerset(weights):
# if sum(x) <= w:
# print(x)
# powersets.append(len(x))
# Because you said no for loops somewhere:
powersets = [len(x) for x in powerset(weights) if sum(x) <= W]
print(max(powersets))
calc_max_baggage(weights, W)这是从以下方面提出来的：
https://docs.python.org/3/library/itertools.html#itertools-recipes
希望这能有所帮助:)
免责声明:有效的python3代码。不确定更改print以删除圆括号是否有效，但您可以尝试:)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53638290
复制相关文章
相似问题