Minimum coins for a change

Finding the minimum number of coins for exchanging a coin of bigger value.

The minimum coins change programming problem is as below.
Given.
a) A coin of bigger value to be changed. Say a coin of value $ 10 is to be changed.
b) A set of available coins. The assumption is that we have a set of infinite coins of values [$1, $ 4, $ 9, $ 16].
The goal is to find the minimum number of smaller coins for exchanging a coin of bigger value i.e $ 10 with coins of smaller values.

Example:
If a coin of value $ 10 is to be changed with coins of values [ $ 1, $ 4, $ 9, $ 16 ] such that we get the minimum coins
a) $ 10 = $ 1 + $ 9 i.e (2 coins)
b) $ 10 = $ 1 + $ 1 + $ 1 … + $ 1 (10 times) (10 coins)
c) $ 10 = $ 1 + $ 1 + $ 4 + $ 4 (4 coins)
Thus minimum coins that we need is 2.

Minimum_Coins_For_Change

Solving minimum coins for change problem

We begin by finding the minimum number of coins for each denomination from $ 1 till the denomination of bigger coin i.e $ 10. using the coins from the available set.

Thus,

  • Base case : We need 0 coins for making a change for $ 0. i.e DP [ 0 ] = 0
  • For $ 1 we need only 1 coin from the set. (i.e $ 1). We store this value in a DP table. i.e DP [ 1 ] = 1. i.e for exchanging $ 1 we need a minimum on 1 coin.
  • For $ 2 we being by using $ 1 coin from the set i.e 1 coin but we still need to find the minimum number of coins needs for remaining $ 1 i.e the deficit as $ 2 - $ 1 = $ 1.
    Now we can use DP table to fetch the minimum number of coins used to make change for $ 1; i.e value of DP [ 1 ] which is 1.
    So for $ 2 we can make change using 2 coins.
    i.e $ 2 = 1 + (DP [ $ 2 - $ 1 ])
    $ 2 = 1 + DP [ 1 ] = 1 + 1 = 2
  • For $ 9 we need only 1 coin from the set i.e $ 9 coin.
  • From $ 10 we can use 1 coin of value $ 9 but for the remaining $ 1 ( $ 10 - $ 9 ), we make use of DP [ 1 ].
    i.e $ 10 = 1 + DP [ $ 10 - $ 9]
    i.e $ 10 = 1 + DP [ $ 1 ]
    i.e $ 10 = 1 + 1 = 2 coins.

C++ Program for finding the minimum number of coins for changing a bigger coin using dynamic programming.

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

class Coins {

    public:

    void GetNumCoins(vector<int>& coinset, int biggercoin) {

        const int MAX = 999999999;
        vector<int> mincoins(biggercoin+1, MAX);

        // 0 is the minimum number of coins needed for changing a bigger coin of value 0
        mincoins[0] = 0;  
            
        for (int val=1; val<=biggercoin; val++) {
            for (int c=0; c<coinset.size(); c++) {
                if (val >= coinset[c]) {
                    mincoins[val] = min( mincoins[val-coinset[c]] + 1, mincoins[val] );
                }   
            }   
        }   

        int val = 0;
        cout << "Value | Minimum Coins" << endl;
        for (const auto& c : mincoins) {
            cout << val << "      " << c << endl;
            val++;
        }   

        cout << mincoins[biggercoin] << " are needed to change value : " << biggercoin << endl;
    }   
};

int main() {

    Coins c;
    vector<int> coinset = { 1, 4, 9, 16 };
    int biggercoin = 10; 
    cout << "Coin set" << endl;
    for(const auto& i : coinset)  
        cout << i << " ";
    cout << endl;
    cout << "Coin to be changed :" << biggercoin << endl;
    c.GetNumCoins(coinset, biggercoin);
    return 0;
}

Output of minimum coins needed to change a bigger coin implemented in C++11

Coin set
1 4 9 16 
Coin to be changed :10
Value | Minimum Coins
0      0
1      1
2      2
3      3
4      1
5      2
6      3
7      4
8      2
9      1
10      2
2 are needed to change value : 10

Copyright (c) 2020, Algotree.org.
All rights reserved.