背包任务中所有组合的数量

Question

有一个经典的背包问题。我对这个问题的版本有点不同。

给定一组物品，每个物品都有一个质量，确定包装物品的组合数量，以便总重量小于或等于给定的限制。

例如，有 5 个质量为： 的项目1, 1, 3, 4, 5。有一个错误limit = 7。有以下组合：

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

有没有办法计算组合数量而不用蛮力？

Answer 1

这是一种解决方案：

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)

印刷：

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