algorithmcombinationsdynamic-programming

Number of all combinations in Knapsack task


There is a classic Knapsack problem. My version of this problem is a little different.

Given set of items, each with a mass, determine the number of combinations to pack items so that the total weight is less than or equal to a given limit.

For example, there is 5 items with mass: 1, 1, 3, 4, 5. There is a bug with limit = 7. There are the following combinations:

1 + 3
1 + 4
1 + 5
1 + 1 + 3
1 + 1 + 4
1 + 1 + 5
3
3 + 4
4
5

Is there a way to count number of combinations without brute?


Solution

  • This is one solution:

    items = [1,1,3,4,5]
    knapsack = []
    limit = 7
    
    def print_solutions(current_item, knapsack, current_sum):
        #if all items have been processed print the solution and return:
        if current_item == len(items):
            print knapsack
            return
    
        #don't take the current item and go check others
        print_solutions(current_item + 1, list(knapsack), current_sum)
    
        #take the current item if the value doesn't exceed the limit
        if (current_sum + items[current_item] <= limit):
            knapsack.append(items[current_item])
            current_sum += items[current_item]
            #current item taken go check others
            print_solutions(current_item + 1, knapsack, current_sum )
    
    print_solutions(0,knapsack,0)
    

    prints:

    []
    [5]
    [4]
    [3]
    [3, 4]
    [1]
    [1, 5]
    [1, 4]
    [1, 3]
    [1]
    [1, 5]
    [1, 4]
    [1, 3]
    [1, 1]
    [1, 1, 5]
    [1, 1, 4]
    [1, 1, 3]