The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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