changemaking.cpp

#include<iostream>
using namespace std;
int d[4]={1,2,5,10};//denomination array
int k=4;//number of denomination
void getMinimumNumberOfChanges(int n){
  //c[i] => array to store the minimum number of coins required to value i
  //s[i] => array to store the last coin required to get the value i
  int c[n],s[n],min,coin;
  c[0]=0;

  //DP is all about splitting in the problem into many sub problems
  //here we first find no. of changes for p=1 then ,p=2 ,......till p= n which is the required value
  //so first for loop runs from p=1 to n
  for(int p=1;p<=n;p++){
       min=999;
       considering all possible denominations from array index 0 to k-1
      for(int i=0;i<k;i++){
        if(d[i]<=p){
          if(1+c[p-d[i]]<min){
            min=1+c[p-d[i]];
            coin=i;
          }
        }
      }
      c[p]=min;
      s[p]=coin;
  }
 cout<<"Minimum no. of coins required "<<c[n];
 cout<<"coins are"<<'\n';
 //this while loop is for tracing the coins.the code is self explanatory
 while(n>0){
  cout<<d[s[n]]<<"\n";
  n=n-d[s[n]];
 }
}