###### Problem statement

Let given weights & values of **n** items to be put in a knapsack of capacity **W** ie.

We’ve 2 integer arrays `value[0..n-1]`

and `weight[0...n-1]`

. The objective is to find out the maximum value subset of `value[]`

array such that sum of weight of subset is smaller or equal to W.

###### Optimal Substructure

An optimal solution to problem contains optimal solution to subproblems. To consider all subset of items, **2 cases for every item arises:**

- Item is included in optimal set
- Item is not included in optimal set

Therefore, max value obtained from n items is maximum of the following:

- Maximum value obtained by n-1 items and w weight, excluding nth item.
- Value of nth item + maximum value obtained by n-1 items and w – weight of nth item (including nth item).

If weight of nth item is greater than W, nth item cannot be included.

###### Overlapping Subproblems

**A recursive solution:** (Top down approach)

```
int knapsack (int W, int wt[], int val[], int n) {
//Base case
if (n == 0 || W == 0) {
return 0;
}
if (wt[n-1] > W) {
// Excluding item val[n-1]
return knapsack(W, wt, val, n-1);
} else {
//including item val[n-1] if it results in greater value
return max ((val[n-1] + knapsack(W-wt[n-1], wt, val, n-1)),
knapsack(W, wt, val, n-1));
}
}
```

**Main function**

```
int main () {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50, n = 3;
printf("%d", knapsack(W, wt, val, n));
return 0;
}
```

Here’s a running example: Recursive Knapsack

###### Understanding the problem in this approach

Here, certain subproblems are recomputed. Let’s see how,

wt[ ] = {1, 1, 1}, val[ ] = {10, 20, 30}, n=3, W = 2.

Now, K(n, W)

Recomputations can be avoided by exploiting overlapping subproblems property ie. by constructing a temporary array K[n][W] in bottom up manner.

Here’s the code:

```
int knapsack (int W, int wt[], int val[], int n) {
int K[n+1][W+1] = {0};
// Building table K[n][W] in bottom manner
for(int i=0; i<=n; i++) {
for(int w=0; w <= W; w++) {
// Base case: empty knapsack
if (i == 0 || w == 0) {
K[i][w] = 0;
} else if (wt[i-1] <= w) {
// Selecting val[i-1] if it gives higher knapsack value
K[i][w] = max((val[i-1] + K[i-1][w-wt[i-1]]),
K[i-1][w]);
} else {
// Not including val[i-1]: if wt[i-1] is greater than
// available knapsack capacity
K[i][w] = K[i-1][w];
}
}
}
return K[n][W];
}
```

Here’s a working example: Knapsack Solution

Time complexity of this solution is **O(n*W)**.

In the next post, we’ll learn about, how to find the actual Knapsack items that were selected.

Adios!

## 3 thoughts on “Knapsack Problem (Dynamic Programming)”