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

+3

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:

``````[]



[3, 4]

[1, 5]
[1, 4]
[1, 3]

[1, 5]
[1, 4]
[1, 3]
[1, 1]
[1, 1, 5]
[1, 1, 4]
[1, 1, 3]
```

```
+3

source

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)
```

```
+2

source

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],,[4,3],[4,1,1],[4,1],[4,1],,[3,1,1],[3,1],[3,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, ...)

+2

source

All Articles