This is a C++ Program that Solves Coin Change Problem using Dynamic Programming technique.
There are infinite number of coins of x different values. These values are given. Using these coins, you have to make change for Rs. N. In how many ways, you can make this change?
Note that there are infinite number of coins of each given value.
This problem can be solved by using Bottom-up dynamic programming. First we will calculate the no. of ways to change a smaller amount. This can be calculated by finding out no. of ways to change the required amount by once including a coin and once excluding it. Then we will store this value in a matrix. Now, using these values, we will calculate the result for a bigger amount.
The time complexity of this solution is O(N*x).
Case-1:
N=10 x=4 coin[]={2,5,3,6} Expected result=5 Possible combinations are - 2+2+2+2+2 5+5 2+3+5 2+2+3+3 2+2+6
Case-2:
N=4 x=3 coin[]={1,2,3} Expected result=4 Possible combinations are - 1+1+1+1 1+1+2 1+3 2+2
Here is source code of the C++ Program to Solve Coin Change Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<iostream>
using namespace std;
int coinChange(int coin[], int x, int N)
{
int i,j;
//make a matrix of size (N+1)*x to tabulate the computed values
int dp[N+1][x];
//dp[i][j] represents no.of ways in which change of Rs. i can be made with just j type of coins available
int including,excluding;
//initialization
//since, there is only one way in which change of Rs. 0 can be made ie., not including any coin
for(j=0;j<x;j++)
{
dp[0][j]=1;
}
//i represents the amount whose change is required
for(i=1;i<=N;i++)
{
//j represents the coin values available
for(j=0;j<x;j++)
{
//if the the value of current coin is less than or equal to total amount whose change is required
//include this coin
if(i>=coin[j])
{
including=dp[i-coin[j]][j];
}
else
including=0;
//excluding will store the number of ways in which the amount can be changed without including the current coin value
if(j>=1)
excluding=dp[i][j-1];
else
excluding=0;
//dp[i][j] will be the sum of no.of ways by including as well as excluding the current coin
dp[i][j]=including+excluding;
}
}
return dp[N][x-1];
}
int main()
{
int i;
int x; //number of distinct values of coins
int N; //amount whose change is required
cout<<"Enter the amount whose change is required"<<endl;
cin>>N;
cout<<"Enter the number of distinct values of coins"<<endl;
cin>>x;
//distinct values of coins
int coin[x];
cout<<"Enter the values of coins"<<endl;
for(i=0;i<x;i++)
cin>>coin[i];
cout<<"No. of ways in which Rs."<<N<<" can be changed is ";
cout<<coinChange(coin,x,N);
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 coinChange as parameters. This function will calculate the expected result and return it. The returned value will be displayed.
Case-1: $ g++ coin_change.cpp $ ./a.out Enter the amount whose change is required 10 Enter the number of distinct values of coins 4 Enter the values of coins 2 5 3 6 No. of ways in which Rs.10 can be changed is 5
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Buy Programming Books
- Apply for Information Technology Internship
- Practice Computer Science MCQs
- Practice Design & Analysis of Algorithms MCQ
- Apply for Data Structure Internship