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

Back | Next

All problems on Dynamic Programming
* Find the nth term of fibonacci series
* Evaluate combination(n, r)
* Solve the Edit-Distance problem
* Longest Common Subsequence ( LCS ) problem
* Given a set of coin denominations, find the minimum number of coins required to make a change for a target value
* Longest Increasing Subsequence ( LIS ) problem
* Unbounded Knapsack problem
* 0/1 Knapsack problem
* Splitting a string into minimum number of palindromes
About    Contact    Sitemap    Terms    Privacy