首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >如何找到最多为一个常量的所有组合?

如何找到最多为一个常量的所有组合?
EN

Stack Overflow用户
提问于 2017-10-26 05:56:10
回答 1查看 1.6K关注 0票数 0

P=[P1, P2, ..., Pk]k正整数,T为正整数。我想生成所有的组合,这些组合的总和最多为T。即sum(x[i] * P[i] for i in 1:k) <= T,其中x[i] = 1i在组合中被选择。

举例说明。

P=[1, 2, 3]T=4。组合应该是:

代码语言:javascript
复制
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中可以用来生成此类组合的任何函数,您可以提供它。

谢谢。

EN

回答 1

Stack Overflow用户

发布于 2017-10-26 06:07:27

这类似于子集求和问题(在评论中提到),除了找到等于目标的数字求和。您希望找到总和小于或等于目标的数字。

尽管如此,可以使用与动态编程类似的方法:

代码语言:javascript
复制
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

演示:

代码语言:javascript
复制
>>> for subset in subset_sum([1, 2, 3], target=4):
...     print(*subset, sep='+')
...     
1
2
1+2
3
1+3
票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/46942681

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档