Number of all combinations in Knapsack task

Question

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?

Answer 1

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]

Answer 2

well as others posted some solutions too, here is a translation of the naive extension of the problem using Haskell and simple recursion:

combinations :: Int -> [Int] -> [[Int]]
combinations _ [] = [[]]
combinations w (x:xs)
  | w >= x = [ x:ys | ys <- combinations (w-x) xs] ++ combinations w xs
  | otherwise = combinations w xs

test-run

λ> combinations 7 [5,4,3,1,1]
[[5,1,1],[5,1],[5,1],[5],[4,3],[4,1,1],[4,1],[4,1],[4],[3,1,1],[3,1],[3,1],[3],[1,1],[1],[1],[]]

what's going on?

starting with 5 you have two choices: either you take it or not.

• if you take it you have limit 2 left and so you should recursively look for how many ways you can do this
• if not you still have limit 7 but only 1,1,3,4 to look for ....

the algorithm translates this into basic Haskell in a hopeful readable way - feel free to ask for details

remarks

I did not look at the performance at all - but it should be easy doing the same stuff you would do with the original problem (rewrite columns of the table, ...)