Coins Change Problem

The coins change programming problem is described 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.

Coin_Change

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 : 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.

Implementation of coins change problem 

from typing import List # For annotations

def DPGetChange (coinset : List[int], biggercoin : int) -> int :

    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 : List[int], numcoins : int, biggercoin : int) -> int :

    # 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

list_biggercoin = [4, 6, 10, 10]
coin_set = [ [ 1, 2, 3 ], [ 2, 3, 4 ], [ 2, 5, 8, 9, 10 ], [ 8, 9, 10 ] ]
# Bigger coin 4, coinset [ 1, 2, 3 ] # Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3)
# Bigger coin 6, coinset [ 2, 3, 4 ] # Three ways : (2,2,2) (2,4) (3,3)
# Bigger coin 10, coinset [ 2, 5, 8, 9, 10 ] # Four ways : (2,2,2,2,2) (2,8) (5,5) (10)
# Bigger coin 10, coinset [ 8, 9, 10 ] # 1 way : (10)

for i in range(len(list_biggercoin)) :
    print("\nCoin set : " + str(coin_set[i]) + " Bigger coin : " + str(list_biggercoin[i]), end = ' ')
    print("# [DP] Ways : " + str (DPGetChange(coin_set[i], list_biggercoin[i])), end = ' ')
    print("\nCoin set : " + str(coin_set[i]) + " Bigger coin : " + str(list_biggercoin[i]), end = ' ')
    print("# [Recursion] Ways : " + str(GetChange(coin_set[i], len(coin_set[i]), list_biggercoin[i])), end = ' ')

Output

Coin set : [1, 2, 3] Bigger coin : 4 # [DP] Ways : 4 
Coin set : [1, 2, 3] Bigger coin : 4 # [Recursion] Ways : 4 
Coin set : [2, 3, 4] Bigger coin : 6 # [DP] Ways : 3 
Coin set : [2, 3, 4] Bigger coin : 6 # [Recursion] Ways : 3 
Coin set : [2, 5, 8, 9, 10] Bigger coin : 10 # [DP] Ways : 4 
Coin set : [2, 5, 8, 9, 10] Bigger coin : 10 # [Recursion] Ways : 4 
Coin set : [8, 9, 10] Bigger coin : 10 # [DP] Ways : 1 
Coin set : [8, 9, 10] Bigger coin : 10 # [Recursion] Ways : 1

#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

class CoinsChange {

    // DP solution for making coin change
    int DPGetChange (int[] coinset, int biggercoin) {
    
        int num_coins = coinset.length;
        int[][] dptable = new int[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 (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
    }   

    void Display (int coin, int[] coin_set) {
        System.out.println("Coin to change : " + coin);
        System.out.print("Coin set : ");
        for (int i=0; i<coin_set.length; i++) {
            System.out.print(coin_set[i] + " ");
        } System.out.println();
    }   
    
    public static void main(String[] args) {
    
        int coin1 = 4;
        int[] coinset_1 = { 1, 2, 3 }; /* Four ways : (1,1,1,1) (1,1,2) (2,2) (1,3) */
    
        int coin2 = 6;
        int[] coinset_2 = { 2, 3, 4 }; /* Three ways : (2,2,2) (2,4) (3,3) */
    
        int coin3 = 10; 
        int[] coinset_3 = { 2, 5, 8, 9, 10 }; /* Four ways : (2,2,2,2,2) (2,8) (5,5) (10) */
    
        CoinsChange c = new CoinsChange();

        System.out.println("Number of ways of making coin change using dynamic programming");
        c.Display(coin1, coinset_1);
        System.out.println("Ways : [" + c.DPGetChange(coinset_1, coin1) + "]");
        c.Display(coin2, coinset_2);
        System.out.println("Ways : [" + c.DPGetChange(coinset_2, coin2) + "]");
        c.Display(coin3, coinset_3);
        System.out.println("Ways : [" + c.DPGetChange(coinset_3, coin3) + "]");
    
        System.out.println("\nNumber of ways of making coin change using recursion");
        c.Display(coin1, coinset_1);
        System.out.println("Ways : [" + c.GetChange(coinset_1, coinset_1.length, coin1) + "]"); 
        c.Display(coin2, coinset_2);
        System.out.println("Ways : [" + c.GetChange(coinset_2, coinset_2.length, coin2) + "]"); 
        c.Display(coin3, coinset_3);
        System.out.println("Ways : [" + c.GetChange(coinset_3, coinset_3.length, coin3) + "]"); 
    }   
}

Output

Number of ways of making coin change using dynamic programming
Coin to change : 4
Coin set : 1 2 3 
Ways : [4]
Coin to change : 6
Coin set : 2 3 4 
Ways : [3]
Coin to change : 10
Coin set : 2 5 8 9 10 
Ways : [4]

Number of ways of making coin change using recursion
Coin to change : 4
Coin set : 1 2 3 
Ways : [4]
Coin to change : 6
Coin set : 2 3 4 
Ways : [3]
Coin to change : 10
Coin set : 2 5 8 9 10 
Ways : [4]

Copyright (c) 2019-2022, Algotree.org.
All rights reserved.