find number of unique durations given a list of durations and an upper bound

Question

Lets say we are given a list of durations (5s, 10s, 10s, 15s, 15s, 15s, 25s, 30s....) and we want to find a list of unique durations that can be created using this list of single durations.

for example if we have the original list of (5, 5, 15, 25) we can create the following durations:

• 5 - using one 5 element
• 10 - using two 5 elements
• 15 - using one 15 element
• 20 - using one 5 element and one 15 element
• 25 - using two 5 elements and one 15 element OR using the 25 element
• 30 - using 25 and 5
• 35 - using 25 and two 5s
• 40 - using 25 and 15
• 45 - using 25, 15 and 5
• 50 - using all elements

As a bonus I want to set an upper limit. For example I want to use a an upper bound for the total duration of 37.

This should eliminate the options of 40, 45, and 50 because they are above the limit.

PS, durations are very frequently repeated in the original list, so maybe there's an optimisation possible there?

Anyone know of a way to approach this?

I have used combinatorics libraries to find all possible combinations using the element limit, and eliminate ones that are above the max limit, but the number grows with factorial complexity which made the solution way too slow.

Answer 1

Make a table T of size upper limit + 1, put 1 into T[0], or define set containing zero value. Then for every value v (duration) check for nonzero entries of table (say index i) and put 1 into v+i cell.

Python example with set:

a = [4,13,29]
lim = 37
t = {0}
for v in a:
    for i in range(lim - v + 1):
        if i in t:
            t.add(i + v)
t.remove(0)
print(len(t), t)

>> 19  {4, 8, 12, 13, 16, 17, 20, 21, 24, 25, 26, 28, 29, 30, 32, 33, 34, 36, 37}