This is a C++ Program that Solves Change Making Problem using Dynamic Programming technique.
There are infinite number of coins of n different values. These values are given. Using these coins, you have to make change for Rs. Sum. Find the minimum number of coins required to change Rs. Sum.
Note that the problem is different from coin change problem. In coin change problem, we were asked to find out in how many ways the change can be made. In this problem, we are supposed to find out the minimum number of coins required to change.
We will solving this problem in bottom up manner. We will first calculate the result for smaller value of sum and store the result in a matrix and use the stored values to compute results for higher value of sum.
Case-1:
Sum=11 n=4 coin[]={1,5,6,8} Expected result=2 using 5 and 6
Here is source code of the C++ Program to Solve Change Making Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
int changeMaking(int coin[], int n, int sum)
{
int i,j;
int x,y;
//matrix to tabulate results
int dp[n+1][sum+1];
//dp[i][j]=minimum no. of coins required to change j using only i coins
//initialization
//if there is no coin, then infinite no. of coins will be required to change j
for(j=0;j<=sum;j++)
dp[0][j]=INT_MAX;
//if value to be changed is 0, then no coin is required
for(i=1;i<=n;i++)
dp[i][0]=0;
//i represents the number of coins being used
for(i=1;i<=n;i++)
{
//j represents the amount whose change is required
for(j=1;j<=sum;j++)
{
//if the value of current coin is less than or equal to the amount whose change is required, then first include the coin and then exclude the coin
//compare both the results and select the one which takes minimum no. of coins
if(j>=coin[i-1])
{
//without including the current coin
x=dp[i-1][j];
//the current coin is included(hence 1+)
y=1+dp[i][j-coin[i-1]];
//the lesser value out of both is taken
dp[i][j]=min(x,y);
}
//If value of current coin is greater than the amount, this coin can not be included
else
dp[i][j]=dp[i-1][j];
}
}
return dp[n][sum];
}
int main()
{
int i;
int n,sum;
cout<<"Enter the amount whose change is required"<<endl;
cin>>sum;
cout<<"Enter the number of coins available"<<endl;
cin>>n;
int coin[n];
cout<<"Enter the values of coins"<<endl;
for(i=0;i<n;i++)
cin>>coin[i];
cout<<"The least number of coins whose sum is equal to required sum is"<<endl;
cout<<changeMaking(coin,n,sum);
cout<<endl;
return 0;
}
In the main function, we ask the user to input the amount of change required, number of coins available and the value of coins. We pass these values to the function changeMaking as parameters. This function will calculate the expected result and return it. The returned value will be displayed.
Case-1: $ g++ change_making.cpp $ ./a.out Enter the amount whose change is required 11 Enter the number of coins available 4 Enter the values of coins 1 5 6 8 The least number of coins whose sum is equal to required sum is 2
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Check Computer Science Books
- Check Programming Books
- Practice Programming MCQs
- Practice Computer Science MCQs
- Check Data Structure Books