如何找到总和最多为一个常数的所有组合? [英] How to find all combinations that sum up to at most a constant?

问题描述

让P=[P1, P2, ..., Pk]为k正整数，让T为正整数.我想生成所有最多合计为T的组合.也就是说，在组合中选择了x[i] = 1且i的sum(x[i] * P[i] for i in 1:k) <= T.

Let P=[P1, P2, ..., Pk] be k positive integers and let T be a positive integer. I would like to generate all combinations that sum up to at most T. That is, sum(x[i] * P[i] for i in 1:k) <= T where x[i] = 1 iff i is chosen in the combination.

示例.

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

1
2
3
1, 2
1, 3
2, 3

因此，只有组合1, 2, 3不能存在，因为1 + 1 + 3 = 5 > 4.

So only the combination 1, 2, 3 cannot be there because 1 + 1 + 3 = 5 > 4.

我想到先生成所有组合，然后开始验证约束sum(x[i] * P[i] for i in 1:k) <= T.但是这种方法可能比其他聪明的方法更耗时.我们如何生成这样的组合?

I thought of generating all combinations first and then start verifying the constraint sum(x[i] * P[i] for i in 1:k) <= T. But this approach could be more time consuming than other clever approaches. How can we generate such combinations?

NB.如果您知道Python或Matlab中可用于生成此类组合的任何函数，则可以提供它.

NB. If you know any function in Python or Matlab that can be used to generate such combinations, you can provide it.

谢谢.

推荐答案

这类似于子集和问题(在注释中提到)，除了那是关于寻找与目标相等等于的数字.您想找到总数等于目标的小于或等于的数字.

This is like the subset sum problem (mentioned in the comments), except that's about finding numbers summing equal to a target. You want to find numbers summing to a total less-than-or-equal to the target.

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

Nonetheless, a similar approach with dynamic programming can be used:

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

这篇关于如何找到总和最多为一个常数的所有组合?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！