The coins change programming problem is as below. Given. a) Coin to be changed. Say a coin of value $ 4 is to be changed. b) Set of available coins. Assumption is that, we have a set of infinite coins of values [$ 2, $ 4] Goal is to find the number of ways of exchanging a coin of bigger value with coins of smaller values.
Example: If a coin of value $ 4 is to be changed with coins of values [$ 2, $ 4], we have 2 ways a) $ 4 = $ 2 + $ 2 b) $ 4 = $ 4 Thus we have 2 ways.
Recurrence relation for coins change problem
Base cases:
Note: a) When the chosen coin is not included in the available set of coins, the num_coins is reduced by 1. b) When the chosen coin is to be included for coin exchange, the bigger coin value is reduced by the denomination of the chosen coin.
Thus we have the below recurrence equation, Count_MakeChange (num_coins, coin_value, denominations) = Count_MakeChange (num_coins - 1, coin_value, denominations) + Count_MakeChange (num_coins, coin_value - denominations [ num_coins - 1 ], denominations); Note: If the current coin is chosen for making a change, then the value of the bigger coin is reduced to coin_value - denominations [ num_coins - 1 ]
Dynamic programming approach for coins change problem
Base case values for coin change problem
Note: A coin of value $ 0 is included in the set of available coins for making change. This is useful for generating the base cases.
Make change for value | Using denomination | Ways | Hint |
---|---|---|---|
$ 0 | $ 0 | 1 way () | Coin $ 0 can be obtained using coin $ 0 by choosing coin $ 0. |
$ 0 | $ 0, $ 2 | 1 way ($ 0) | Coin $ 0 can be obtained using coins $ 0, $ 2 by choosing coin $ 0. |
$ 0 | $ 0, $ 2, $ 4 | 1 way ($ 0) | Coin $ 0 can be obtained using coins $ 0, $ 2, $ 4 by choosing coin $ 0. |
$ 1 | $ 0 | 0 ways () | Coin $ 1 cannot be obtained using coin $ 0. |
$ 2 | $ 0 | 0 ways () | Coin $ 2 cannot be obtained using coin $ 0. |
$ 3 | $ 0 | 0 ways () | Coin $ 3 cannot be obtained using coin $ 0. |
$ 4 | $ 0 | 0 ways () | Coin $ 4 cannot be obtained using coin $ 0. |
Example: Consider making change for $ 4 coin. Coins available in the set contains coins of value [ $ 2, $ 4 ]. i.e Filling value in table [ 2 ] [ 4 ]
We get the following cases: Case a) $ 4 coin is chosen from the set of available coins for making change. Case b) $ 4 coin is not chosen i.e only coins of value $ 0 and $ 2 are available for making change.
From the recurrence equation
Count_MakeChange [ num_coins ] [ bigger_coin_value ] = Count_MakeChange [ num_coins ] [ bigger_coin_value - value [ coin_selected_from_set ] ] +
Count_MakeChange [ num_coins - 1 ] [ bigger_coin_value ]
Thus we get, Count_MakeChange [ 2 ] [ 4 ] = Count_MakeChange [ 2 ] [ 4 - 4 ] + Count_MakeChange [ 1 ] [ 4 ] Count_MakeChange [ 2 ] [ 4 ] = Count_MakeChange [ 2 ] [ 0 ] + Count_MakeChange [ 1 ] [ 4 ] Count_MakeChange [ 2 ] [ 4 ] = 1 + 1 = 2 ways
Time complexity of coins change problem using dynamic programming : O(n*m), where n is the bigger coin to be exchanged and m is the number of smaller coins to be used for exchanging.
Python
C++ Coins change problem
#include<iostream>
#include<vector>
using namespace std;
// DP solution for making coin change
int DPGetChange (vector<int>& coinset, int biggercoin) {
int num_coins = coinset.size();
int dptable[num_coins+1][biggercoin+1];
// Coins of values greater than 0 cannot be obtained with coins of value 0
for (int c=1; c<=biggercoin; c++) {
dptable[0][c] = 0;
}
// Coin of value 0 can be obtained with any given coins in 1 way
for (int r=0; r<=num_coins; r++) {
dptable[r][0] = 1;
}
for (int r=1; r<=num_coins; r++) {
for (int c=1; c<=biggercoin; c++) {
if (c >= coinset[r-1]) {
// Exclude last coin in the coinset + Include last coin in the coinset
dptable[r][c] = dptable[r-1][c] + dptable[r][c-coinset[r-1]];
} else {
dptable[r][c] = dptable[r-1][c]; // Exclude last
}
}
}
return dptable[num_coins][biggercoin];
}
// Recursive solution for making coin change
int GetChange (vector<int>& coinset, int numcoins, int biggercoin) {
// Coin of value 0 can be obtained with any given values in 1 way
if (biggercoin == 0)
return 1;
// With no available coins for change, we cannot obtain any value
if (numcoins == 0)
return 0;
if (biggercoin >= coinset[numcoins-1])
return GetChange (coinset, numcoins-1, biggercoin) + // Get change excluding the last coin in the coin set
GetChange (coinset, numcoins, biggercoin-coinset[numcoins-1]); // Get change including the last coin in the coin set
else
return GetChange (coinset, numcoins-1, biggercoin); // Get change excluding the last coin
}
int main(){
int coin1 = 4;
vector<int> coinset_1 = { 1, 2, 3 }; /* Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3) */
int coin2 = 6;
vector<int> coinset_2 = { 2, 3, 4 }; /* Three ways : (2,2,2) (2,4) (3,3) */
int coin3 = 10;
vector<int> coinset_3 = { 2, 5, 8, 9, 10 }; /* Four ways : (2,2,2,2,2) (2,8) (5,5) (10) */
cout << "Number of ways of making coin change using dynamic programming" << endl;
cout << DPGetChange (coinset_1, coin1) << endl;
cout << DPGetChange (coinset_2, coin2) << endl;
cout << DPGetChange (coinset_3, coin3) << endl;
cout << "Number of ways of making coin change using recursion" << endl;
cout << GetChange (coinset_1, coinset_1.size(), coin1) << endl;
cout << GetChange (coinset_2, coinset_2.size(), coin2) << endl;
cout << GetChange (coinset_3, coinset_3.size(), coin3) << endl;
return 0;
}
Output of coin change problem.
Number of ways of making coin change using dynamic programming
4
3
4
Number of ways of making coin change using recursion
4
3
4