algorithmtime-complexitycombinationsknapsack-problem

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


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:

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.


Solution

  • 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}