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?

回答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]

回答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, ...)

回答3:

EACH ITEM USED UNLIMITED TIMES

This is rather straightforward extension of original problem.

As you probably know you use DP to solve original problem, where weight of items must be exactly W. When you finish with DP, you will also have solution for all weights < W. To get your solution simply sum up solutions for weights from 1 to W (and +1 for empty set).

EACH ITEM USED ONCE

In this case, there is not other way, but to brute-force all possible combinations. This problem is NP-hard and will have time complexity of O(2^n).

To brute-force use next code (borrowed from @pjsofts):

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)