# 0-1 Knapsack problem

In 0-1 Knapsack problem, we are given a set of items, each with a weight and a value and we need to determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Please note that the items are indivisible; we can either take an item or not (0-1 property). For example,

Input:
value = [ 20, 5, 10, 40, 15, 25 ]
weight = [ 1, 2, 3, 8, 7, 4 ]
int W = 10

Output: Knapsack value is 60

value = 20 + 40 = 60
weight = 1 + 8 = 9 < W

The idea is to use recursion to solve this problem. For each item, there are two possibilities –

1. We include current item in knapSack and recurse for remaining items with decreased capacity of Knapsack. If the capacity becomes negative, do not recurse or return -INFINITY.

2. We exclude current item from knapSack and recurse for remaining items.

Finally, we return maximum value we get by including or excluding current item. The base case of the recursion would be when no items are left or capacity becomes 0.

Below C++/Java implementation finds the maximum value that can be attained with weight less than or equal to W recursively by using above relations.

## C++

Output:

Knapsack value is 60

## Java

Output:

Knapsack value is 60

The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

The above solution has an optimal substructure i.e. optimal solution can be constructed efficiently from optimal solutions of its subproblems. It also has overlapping subproblems i.e. the problem can be broken down into subproblems which are reused several times. In order to reuse subproblems solutions, we can apply Dynamic Programming, in which subproblem solutions are Memoized rather than computed over and over again. Below Memoized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values.

## C++

Output:

Knapsack value is 60

## Java

Output:

Knapsack value is 60

The time complexity of above solution is O(nW) where n is the number of items in the input and W is the Knapsack capacity. Auxiliary space used by the program is also O(nW).

We can also solve this problem in bottom-up manner. In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them. The following bottom-up approach computes T[i][j], for each 1 <= i <= n and 0 <= j <= W, which is maximum value that can be attained with weight less than or equal to j and using items up to first i items. It uses value of smaller values i and j already computed. It has the same asymptotic run-time as Memoization but no recursion overhead.

## C++

Output:

Knapsack value is 60

## Java

Output:

Knapsack value is 60     (6 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
Tahir Rauf

It just returns the maximum value we can gain. How can we store the items which actually contribute to final solution? Guest

well explained.. (y) Guest Guest

Technically, the first “dynamic programming” solution is not really a DP solution.
It’s still a recursive solution optimised by memoization. Guest

Hey, I got a ques. How did you come up with the O(nW) complexity in the DP (top down approach) solution? Guest

Hello,

In the second solution, is it ok to create the key based on index “n” only
String key = to_string(n)?

why do we need to append to_string(W)? Guest
SIMRAN SUNIL MAHINDRAKAR

Why won’t the memoized version not work on code::blocks?? Guest

Try using latest version of GCC from MinGW-w64.  `int include = v[n] + knapSack(v, w, n - 1, W - w[n]);`
```// don't include ith element if j-w[i-1] is negative if (w[i-1] > j) T[i][j] = T[i-1][j]; else // find max value by excluding or including the ith item T[i][j] = max(T[i-1][j], T[i-1][j-w[i-1]] + v[i-1]);```