Change Making problem-Dynamic Programming

Problem:

Given a value n, if we want to make change for n cents, and we have infinite supply of each of d = { d1, d2, .. , dm} valued coins, what is the minimum number of coins to make the change?

 

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

view raw changemaking.cpp hosted with ❤ by GitHub