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.

**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 –

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

- 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++ implementation finds the maximum value that can be attained with weight less than or equal to W recursively by using above relations.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <iostream> #include <climits> using namespace std; // Values (stored in array v) // Weights (stored in array w) // Number of distinct items (n) // Knapsack capacity W int knapSack(int v[], int w[], int n, int W) { // base case: Negative capacity if (W < 0) return INT_MIN; // base case: no items left or capacity becomes 0 if (n < 0 || W == 0) return 0; // Case 1. include current item n in knapSack (v[n]) and recurse for // remaining items (n - 1) with decreased capacity (W - w[n]) int include = v[n] + knapSack(v, w, n - 1, W - w[n]); // Case 2. exclude current item n from knapSack and recurse for // remaining items (n - 1) int exclude = knapSack(v, w, n - 1, W); // return maximum value we get by including or excluding current item return max (include, exclude); } // 0-1 Knapsack problem int main() { // Input: set of items each with a weight and a value int v[] = { 20, 5, 10, 40, 15, 25 }; int w[] = { 1, 2, 3, 8, 7, 4 }; // Knapsack capacity int W = 10; // number of items int n = sizeof(v) / sizeof(v[0]); cout << "Knapsack value is " << knapSack(v, w, n - 1, W); return 0; } |

`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 *Memo*ized rather than computed over and over again. Below *Memo*ized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <iostream> #include <unordered_map> #include <climits> using namespace std; // create a map to store solutions of subproblems unordered_map<string, int> lookup; // Values (stored in array v) // Weights (stored in array w) // Number of distinct items (n) // Knapsack capacity W int knapSack(int v[], int w[], int n, int W) { // base case: Negative capacity if (W < 0) return INT_MIN; // base case: no items left or capacity becomes 0 if (n < 0 || W == 0) return 0; // construct a unique map key from dynamic elements of the input string key = to_string(n) + "|" + to_string(W); // if sub-problem is seen for the first time, solve it and // store its result in a map if (lookup.find(key) == lookup.end()) { // Case 1. include current item n in knapSack (v[n]) & recurse for // remaining items (n - 1) with decreased capacity (W - w[n]) int include = v[n] + knapSack(v, w, n - 1, W - w[n]); // Case 2. exclude current item n from knapSack and recurse for // remaining items (n - 1) int exclude = knapSack(v, w, n - 1, W); // assign max value we get by including or excluding current item lookup[key] = max (include, exclude); } // return solution to current sub-problem return lookup[key]; } // 0-1 Knapsack problem int main() { // Input: set of items each with a weight and a value int v[] = { 20, 5, 10, 40, 15, 25 }; int w[] = { 1, 2, 3, 8, 7, 4 }; // Knapsack capacity int W = 10; // number of items int n = sizeof(v) / sizeof(v[0]); cout << "Knapsack value is " << knapSack(v, w, n - 1, W); return 0; } |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <bits/stdc++.h> using namespace std; // Input: // Values (stored in array v) // Weights (stored in array w) // Number of distinct items (n) // Knapsack capacity W int knapSack(int v[], int w[], int n, int W) { // T[i][j] stores the maximum value that can be attained with // weight less than or equal to j using items up to first i items int T[n+1][W+1]; for (int j = 0; j <= W; j++) T[0][j] = 0; // memset (T[0], 0, sizeof T[0]); // do for ith item for (int i = 1; i <= n; i++) { // consider all weights from 0 to maximum capacity W for (int j = 0; j <= W; j++) { // 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]); } } // return maximum value return T[n][W]; } // 0-1 Knapsack problem int main() { // Input: set of items each with a weight and a value int v[] = { 20, 5, 10, 40, 15, 25 }; int w[] = { 1, 2, 3, 8, 7, 4 }; // Knapsack capacity int W = 10; // number of items int n = sizeof(v) / sizeof(v[0]); cout << "Knapsack value is " << knapSack(v, w, n, W); return 0; } |

`Output:`

Knapsack value is 60

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

well explained.. (y)

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

Consider the function prototype –

`int knapSack(int v[], int w[], int n, int W)`

Here v[] and w[] are static and doesn’t contribute to the complexity. n and W are dynamic and knapSack() method can be called for any combination of n and W (n*W times) where in each call we’re doing constant amount of work (assuming unordered_map operations take constant time).

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

We know that in order to solve any DP problem, we need to save subproblem solution somewhere. A subproblem can be defined in terms of dynamic params in the original problem, in this case, both n and W. We can’t define knapsack subproblem only in terms of remaining items n, we would need remaining capacity W of knapsack as well.

Few Tips:

– Use a single dimensional array if subproblem contains only one dynamic input.

– Use a Map if subproblem contains two or more dynamic inputs as 2D or 3D array would consume a lot of space.

Got it … Thanks!!

In the first two codes, the base case W<0 should be before the base case n<0 ||W==0.

Hello, is there any test case on which the solution is failing?

Just change the first element of w array to 3 and W to 26 in above test case, the first two codes produce different results with the third one. The reason is the first two codes can include the first items when the weight left is not enough, and change the order of the two base cases can avoid this error.

Thanks a lot for bringing this to our notice. We will update the code. Happy coding 🙂

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

Try using latest version of GCC from MinGW-w64.

http://mingw-w64.org/doku.php/download