如何找到最多为一个常量的所有组合？
如何找到最多为一个常量的所有组合？
提问于 2017-10-26 05:56:10
设P=[P1, P2, ..., Pk]为k正整数，T为正整数。我想生成所有的组合，这些组合的总和最多为T。即sum(x[i] * P[i] for i in 1:k) <= T，其中x[i] = 1当i在组合中被选择。
举例说明。
让P=[1, 2, 3]和T=4。组合应该是：
1
2
3
1, 2
1, 3
2, 3所以只有组合1, 2, 3不能出现在那里，因为1 + 1 + 3 = 5 > 4。
我想先生成所有的组合，然后再开始验证约束sum(x[i] * P[i] for i in 1:k) <= T。但这种方法可能比其他聪明的方法更耗时。我们如何生成这样的组合呢？
注意：如果您知道Python或Matlab中可以用来生成此类组合的任何函数，您可以提供它。
谢谢。
回答 1
Stack Overflow用户
发布于 2017-10-26 06:07:27
这类似于子集求和问题(在评论中提到)，除了找到等于目标的数字求和。您希望找到总和小于或等于目标的数字。
尽管如此，可以使用与动态编程类似的方法：
def subset_sum(vals, target=0):
sums = {0: [()]} # key=sum, value=list of subsets for the sum
if target in sums:
yield from sums[target] # annoying base case
for val in vals:
items = sums.items() # don't change dict size during iteration
sums = dict(items)
for prev_sum, prev_subsets in items:
sum_ = prev_sum + val
subsets = [s + (val,) for s in prev_subsets]
sums[sum_] = sums.get(sum_, []) + subsets
if sum_ <= target:
yield from subsets演示：
>>> for subset in subset_sum([1, 2, 3], target=4):
... print(*subset, sep='+')
...
1
2
1+2
3
1+3页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/46942681
复制相关文章
相似问题
腾讯云开发者
