#### Dynamic Programming

Problem
0 / 1 Knapsack problem.
Given a set of ‘n’ items having weights { W1,W2,W3,…..,Wn } & values { V1,V2,V3,…..,Vn }
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 ith 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
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);
int val = findMaxValue(weight,values,size,capacity);
cout<<"\nMaximum value that can be fitted :: "<<val;
cout<<endl;
return 0;
}```