python - 如何找到总和最多为一个常数的所有组合？

Question

让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 中可用于生成此类组合的任何函数，您可以提供。

谢谢。

Answer 1

这类似于子集求和问题(在评论中提到)，不同之处在于寻找求和等于的目标。您想要找到总和小于或等于目标的数字。

尽管如此，可以使用与动态规划类似的方法:

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