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

Question

有个经典Knapsack problem .我对这个问题的看法有点不同。

给定一组元素，每个元素都有质量，确定包装元素的组合数量，使总重量小于或等于给定限制。

例如，有 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]