Algotree > Algorithms > Dynamic Programming > Coins Change Problem

Coins Change Problem

Finding the number of ways of exchanging a coin of bigger value with coins of smaller value.

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:

If a coin of value 0 is to be changed, there is always 1 way of getting it changed using any available denominations. Thus,
Count_MakeChange (num_coins, coin_value, denominations) = 1; when the coin_value equals 0
If zero are coins available to make a change, there is no way of getting a change for a coin of value greater than 0. Thus,
Count_MakeChange (num_coins, coin_value, denominations) = 0; when num_coins equals 0 and coin_value > 0.

Try getting the change for the coin of bigger value using a chosen coin from the available set

     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

Coins change problem in Python.

#!/usr/bin/python3

def DPGetChange(coinset, biggercoin) :

    num_coins = len (coinset)
    dptable = [0] * (num_coins+1)
    for r in range (num_coins+1) :
        dptable[r] = [0] * (biggercoin+1);

    # Coins of values(v) greater than 0 cannot be obtained with coins of value 0
    for v in range (1, biggercoin+1) :
        dptable[0][v] = 0;

    # Coin of value 0 can be obtained with any given coins(c) in 1 way
    for c in range (num_coins+1) :
        dptable[c][0] = 1;

    for c in range (1, num_coins+1) :
        for v in range (1, biggercoin+1) :
            if (v >= coinset[c-1]) :
                # Exclude last coin in the coinset + Include last coin in the coinset
                dptable[c][v] = dptable[c-1][v] + dptable[c][v-coinset[c-1]]
            else :
                dptable[c][v] = dptable[c-1][v] # Exclude last coin in the coinset

    return dptable[num_coins][biggercoin];

def GetChange(coinset, numcoins, 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]:
              # Get change excluding the last coin in the coin set + Get change including the last coin in the coin set
       return GetChange(coinset, numcoins-1, biggercoin) + GetChange (coinset, numcoins, biggercoin-coinset[numcoins-1])
    else:
       return GetChange(coinset, numcoins-1, biggercoin) # Get change excluding the last coin as it has a bigger value

biggercoin = 4;
coinset_1 = [ 1, 2, 3 ] # Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3)
print("Using dynamic programming:" + str ( DPGetChange(coinset_1, biggercoin) ) )
print("Using recursion:" + str( GetChange(coinset_1, len(coinset_1), biggercoin) ) )

biggercoin = 6;
coinset_2 = [ 2, 3, 4 ] # Three ways : (2,2,2) (2,4) (3,3)
print("Using dynamic programming:" + str ( DPGetChange(coinset_2, biggercoin) ) )
print("Using recursion:" + str( GetChange(coinset_2, len(coinset_2), biggercoin) ) )

biggercoin = 10;
coinset_3 = [ 2, 5, 8, 9, 10 ] # Four ways : (2,2,2,2,2) (2,8) (5,5) (10)
print("Using dynamic programming:" + str (DPGetChange (coinset_3, biggercoin) ) )
print("Using recursion:" + str( GetChange(coinset_3, len(coinset_3), biggercoin) ) )

biggercoin = 10;
coinset_4 = [ 8, 9, 10 ] # 1 way : (10)
print("Using dynamic programming:" + str (DPGetChange(coinset_4, biggercoin) ) )
print("Using recursion:" + str ( GetChange(coinset_4, len(coinset_4), biggercoin) ) )

Output of coin change problem.

Using dynamic programming:4
Using recursion:4
Using dynamic programming:3
Using recursion:3
Using dynamic programming:4
Using recursion:4
Using dynamic programming:1
Using recursion:1

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

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