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

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