# Knapsack Problem (Dynamic Programming)

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

1. Item is included in optimal set
2. Item is not included in optimal set

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

1. Maximum value obtained by n-1 items and with remaining ‘w’ knapsack weight capacity (excluding the nth item).
2. Value of nth item + maximum value obtained by n-1 items and with ‘w – weight of the nth item’ remaining knapsack weight capacity (including the nth item).
3. If weight of nth item is greater than w (remaining knapsack capacity value), 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.