**Problem :- **

**0 / 1 Knapsack** problem.

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

and a

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

Consider

We have a

We see that, if we pick up weight

we can accomodate a total value of

We will maintain a 2D array

Let us determine the structure of the optimal solution.

Let

We can either select or reject a particular weight.

If the

else there are two possible cases :

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 :

Finally,

**#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;
}