#### Dynamic Programming

**Problem **

**Unbounded 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 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' Then, knapsack[W] -> required answer 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] = 0; items[0] = -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[0]); // 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; }