#### Dynamic Programming

**Problem **

**0 / 1 Knapsack** problem.

Given a set of **‘n’** items having weights **{ W _{1},W_{2},W_{3},…..,W_{n} }** & values

**{ V**

_{1},V_{2},V_{3},…..,V_{n}}and a

**Knapsack**of weight

**W**, find the maximum value that can be accomodated using maximum

1 instance of each weight i.e we can either pick that weight or leave it.

So, the aim is to maximize the value of picked up items such that sum of the weights is less than

or equal to

**W**( Knapsack Weight ).

Consider

**3**items having weights

**{ 2, 3, 5 }**& values

**{ 50, 100, 140 }**.

We have a

**Knapsack**of weight

**5**. We can either pick up a weight or leave it.

We see that, if we pick up weight

**2**& weight

**3**,

we can accomodate a total value of

**150**which is the maximum value that can be collected using the given weights, keeping in mind the constraint that knapsack weight is

**5**.

**Solution **

We will maintain a 2D array **knapsack [ n + 1 ][ W + 1]** where **knapsack [ i ][ j ]** stores the maximum value that can be accomodated in a knapsack of weight **‘ j ‘** using first **‘ i ‘** weights. Then, **knapsack [ n ][ W ]** gives the maximum value that can be fitted in the knapsack of given weight **‘ W ‘** using the given **‘ n ‘** weights.

Let us determine the structure of the optimal solution.

Let **knapsack [ i ][ j ]** denotes the maximum value that can be fitted in the knapsack of capacity **‘ j ‘** using first

**‘ i ‘** weights.

We can either select or reject a particular weight.

If the **i**^{th} i.e **w ( i )** is greater than knapsack capacity **W**, then **knapsack [ i ][ j ] = knapsack [ i – 1 ][ j ]**

else there are two possible cases :

**1 )** Reject the weight **‘ i ‘** : **knapsack [ i ][ j ] = knapsack [ i – 1 ][ j ]**

**2 )** Select the weight **‘ i ‘** : **knapsack [ i ][ j ] = knapsack [ i – 1 ][ j – w ( i ) ] + v ( i )**

Since, we want to maximize the value accomodated in the knapsack, we need to consider the maximum of the two cases. Thus, the structure of the optimal solution defined recursively as :

**knapsack [ i ][ j ] = max ( knapsack [ i – 1 ][ j ] , knapsack [ i – 1 ][ j – w ( i ) ] + v ( i ) )**

Finally, **knapsack [ n ][ W ]** gives the required solution. See the implementation below.

#include<iostream> using namespace std; int max(int a,int b) { return ((a > b) ? a : b); } /* Given n items, each having weight w(i) and value v(i) and a knapsack of weight 'W', find the maximum value that can be accomodated using max 1 instance. Suppose knapsack[i][j] -> max value that can be fitted in a knapsack of weight 'j' using 0...i-1 weights Then, knapsack[W][n] -> required answer Standard Recursive solution :- 1) knapsack[i][j] = knapsack[i-1][j] if w(i) > W 2) knapsack[i][j] = max(knapsack[i-1][j], knapsack[i-1][j-w(i)]+v(i)), else */ int findMaxValue(int weight[],int values[],int n,int capacity) { int i,j; // matrix where each cell (i,j) stores the max value that can be // fitted in a knapsack of weight 'j' using 0...i-1 weights int knapsack[n+1][capacity+1]; for (i=0;i<=n;i++) { for (j=0;j<=capacity;j++) { // Boundary Case if (i == 0 || j == 0) { knapsack[i][j] = 0; } // case 1 of standard recursive formula else if (weight[i-1] > j) { knapsack[i][j] = knapsack[i-1][j]; } // case 2 of standard recursive formula else { knapsack[i][j] = max(knapsack[i-1][j], knapsack[i-1][j-weight[i-1]] + values[i-1]); } } } return knapsack[n][capacity]; } // main int main() { int weight[] = {2,3,5}; int values[] = {50,100,140}; int capacity = 5; // capacity of the knapsack int size = sizeof(weight)/sizeof(weight[0]); int val = findMaxValue(weight,values,size,capacity); cout<<"\nMaximum value that can be fitted :: "<<val; cout<<endl; return 0; }