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?
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]