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 :-
Coin Change problem.
Given a set of coin denominations, find the minimum number of coins required to make a change
for a target value.
Consider a set of denominations as { 1, 2, 5, 9 }.
Suppose we want to make a change for a target value = 13.

There are many possible ways like using
13 coins of denomination 1 ( Total 13 coins )
6 coins of denomination 2 & 1 coin of denomination 1 ( Total 7 coins )
2 coins of denomination 5 with 1 coin each of denomination 1 & 2 ( Total 4 coins )

Minimum no. of coins = 3 ( 1 coin of denomination 9, 2 coins of denomination 2 )

Solution :-
Suppose we are given an array value [ n ] which stores coins of n denominations.
We will maintain an array change [ n + 1 ] where index j of the array stores the minimum number of coins required to make a change for value j. Eventually, change [ x ] will give the solution ( minimum no. of coins required to make a change for target value x ).
Let us find the structure of the optimal solution.
Let change ( j ) denotes the minimum number of coins required to make a change for value ' j '.
Now, to achieve that, we need to decide whether to consider a coin of particular denomination.
So, we will iterate through the array value [ n ] and either choose or reject a coin. If we choose a coin of denomination i , then the problem reduces to 1 + ( No. of coins to make a change for ' j - value ( i ) ' )
Since, our objective is to find minimum no. of coins required to make a change for value j,
we will consider every possible denomination i ( i = 0, 1, ... n ) and find the
minimum ( 1 + ( No. of coins to make a change for ' j - value ( i ) ' ) ) for all values of ' i '.
Thus, the structure of the optimal solution is defined recursively as :
change ( j ) = min [ ( 1 + change ( j - values [ i ] ) ) for i = 0 , 1 , ... , n ]
change ( x ) is the required solution.

#include<iostream>
using namespace std;
#define INF 9999 // denotes a very high value


/* given a set of coin denomination, find the min no. of coins required 
   to make a change for a target value.
   suppose, we are given 'n' denominations in an array 'values' and
   change(j) -> min no. of coins required to make a change for value 'j'
   then change(target) -> required answer
   So we need to create a temporary array change[0...target] where index 'j'
   stores the min no. of coins required to make a change for value j
   Standard Recursive Solution :-
   change[j] = min[ ( 1 + change[j-values[i]] ) for i = 0...n-1 ]       
*/
int minCoins(int values[],int n,int target) {
   // array to store the min no. of coins required to make a change
   // for each index 0...target
   int change[target+1];
   change[0] = 0;
   int i,j;
   for(j=1;j<=target;j++) {
      int min = INF;
      // as per the recursive solution for all i = {0...n-1}     
      for(i=0;i<n;i++) {
         if(j>=values[i] && (change[j-values[i]]+1) < min)
            min = change[j-values[i]]+1;
      }
      // store the minimum no. of coins required to make a change for target = j
      change[j] = min;
   }
   return change[target];
}

//main
int main() {
   int values[] = {1,2,5,9};
   int n = sizeof(values)/sizeof(values[0]);
   int target = 13;
   int min = minCoins(values,n,target);
   cout<<"\nMin no. of coins required :: "<<min;
   cout<<endl;
}

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