#### Dynamic Programming

Problem
Unbounded 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 accommodated using 1 or
more instances of given weights.
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 17. We can use one or more instances of any items to fill the knapsack such that the value that can be accommodated in the knapsack is maximized.
We see that, if we pick up 5 instances of weight 3 & 1 instance of weight 2,
we can accommodate a total value of 550 which is the maximum value that can be collected using the given weights, keeping in mind the constraint that knapsack weight is 17.

Solution
We will maintain an array knapsack [ W + 1 ] where ‘ j ‘ index stores the maximum value that can be fitted in a knapsack of capacity ‘ j ‘.
Then, knapsack [ W ] gives the maximum value that can fitted in the knapsack of given weight i.e ‘ W ‘.
Let us find the structure of the optimal solution.
Let knapsack ( j ) denotes the maximum value that can be fitted in a knapsack of weight ‘ j ‘.
While computing knapsack ( j ), we need to decide whether to select or reject an instance of a weight ‘ i ‘.
If we reject all the weights, then knapsack ( j ) = knapsack ( j – 1 ) and
If we select an instance of weight ‘ i ‘, then
knapsack ( j ) = maximum [ knapsack ( j – W ( i ) ) + V ( i ) for i = 0, … , n – 1 ]
Thus, the structure of the optimal solution is defined recursively as :
knapsack [ j ] = max ( knapsack [ j – 1 ] , { knapsack [ j – w [ i ] ] + v [ i ] for i = 0…n-1 } )
Finally, knapsack [ W ] gives the required solution. In the implementation below, we maintain some additional information to print the selected weights and their no. of instances apart from the maximum value that can be accommodated in the given knapsack.

```#include<iostream>
using namespace std;

// print out the actual weights and their no. of instances used
// to fill the knapsack
void instancesUsed(int items[],int weights[],int capacity,int size) {
int k = capacity;
int instances[size];
int i;
for(i=0;i<size;i++)
instances[i] = 0;
// compute the no. of instances used for each selected item(weight)
while(k >= 0) {
int x = items[k];
if(x == -1) break;
instances[x] += 1;
k -= weights[items[k]];
}
cout<<"\nInstances used :-\n";
for(i=0;i<size;i++)
cout<<weights[i]<<" "<<instances[i]<<endl;
}

/* 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
accommodated using 1 or more instances of given weights.
Suppose knapsack[j] -> max value that can be fitted in a knapsack
of weight 'j'
Standard Recursive solution :-
knapsack[j] = max(knapsack[j-1], {knapsack[j-w(i)]+v(i) for i = 0...n-1})
*/
int findMaxValue(int weight[],int values[],int items[],int n,int capacity) {
// temporary array where index 'j' denotes max value that can be fitted
// in a knapsack of weight 'j'
int knapsack[capacity+1];
knapsack = 0;
items = -1;
int i,j;
for(j=1;j<=capacity;j++) {
items[j] = items[j-1];
// as per our recursive formula,
// iterate over all weights w(0)...w(n-1)
// and find max value that can be fitted in knapsack of weight 'j'
int max = knapsack[j-1];
for(i=0;i<n;i++) {
int x = j-weight[i];
if(x >= 0 && (knapsack[x] + values[i]) > max) {
max = knapsack[x] + values[i];
items[j] = i;
}
knapsack[j] = max;
}
}
return knapsack[capacity];
}

// main
int main() {
int weight[] = {2,3,5};
int values[] = {50,100,140};
int capacity = 17; // capacity of the knapsack
int size = sizeof(weight)/sizeof(weight);
// stores the items and the no. of instances of each item
// used to fill the knapsack
int items[capacity+1];
int val = findMaxValue(weight,values,items,size,capacity);
cout<<"\nMaximum value that can be fitted :: "<<val;
instancesUsed(items,weight,capacity,size);
cout<<endl;
return 0;
}```