The number of all combinations in the Knapsack problem
There is the classic Knapsack problem . My version of this problem is slightly different.
Given a set of items, each with a weight, determine the number of combinations for packing items so that the total weight is less than or equal to the specified limit.
For example, there are five elements with weight: 1, 1, 3, 4, 5
. Error with limit = 7
. The following combinations exist:
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 the number of combinations without being rough?
source to share
This is one of the solutions:
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]
source to share
EACH ITEM USED UNLIMITED TIME
This is a fairly simple extension of the original problem .
As you probably know, you are using DP to solve the original problem, where the element weights must be exactly W. When you are done with DP, you will also have a solution for all weights <W. To get your solution, just summarize the solutions for weights from 1 to W (and +1 for an empty set).
EACH PART USED ONE
In this case, there is no other way than the brute force of all possible combinations. This problem is NP-hard and will have time complexity O (2 ^ n).
To iterate over use the following 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)
source to share
while others have posted some solutions, here is a translation of a 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 happening?
starting at 5, you have two options: either you accept it or you don't.
- If you do this, you have a constraint of 2 to the left and therefore you have to recursively search for how many ways to do it.
- if not, you still have a limit of 7, but only 1,1,3,4 to search ...
the algorithm translates this into basic Haskell with a reliable readable way - feel free to ask for details
remarks
I haven't looked at performance at all, but it should be easy for you to do the same as with the original problem (rewrite table columns, ...)
source to share