0

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.

Example.

Let P=[1, 2, 3] and T=4. The combinations should be: 

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

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

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. If you know any function in Python or Matlab that can be used to generate such combinations, you can provide it.

Thank you.

wim
  • 338,267
  • 99
  • 616
  • 750
Ribz
  • 551
  • 1
  • 4
  • 13

1 Answers1

3

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

Demo:

>>> for subset in subset_sum([1, 2, 3], target=4):
...     print(*subset, sep='+')
...     
1
2
1+2
3
1+3
wim
  • 338,267
  • 99
  • 616
  • 750