Minimum coins for a change
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.
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.
Program for finding the minimum number of coins for changing a bigger coin.
from typing import List
import sys
def GetNumCoins (coinset : List[int], biggercoin : int) :
mincoins = [sys.maxsize] * (biggercoin + 1)
# 0 is the minimum number of coins needed for changing a bigger coin of value 0
mincoins[0] = 0
for val in range(1, biggercoin+1) :
for c in range(len(coinset)) :
if (val >= coinset[c]) :
mincoins[val] = min (mincoins[val-coinset[c]] + 1, mincoins[val])
val = 0
print ("Value | Minimum Coins")
for c in mincoins :
print(str(val) + " " + str(c))
val += 1
print (str(mincoins[biggercoin]) + " coins are needed to change the coin of value (" + str(biggercoin) + ")")
def main() :
coinset = [ 1, 4, 9, 16 ]
biggercoin = 10
print ("Coin set : " + str(coinset))
print ("Coin to be changed : " + str(biggercoin))
GetNumCoins(coinset, biggercoin)
if __name__ == "__main__" :
main()
Output
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 coins are needed to change the coin of value (10)
#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
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
import java.util.Arrays;
import java.lang.Math;
class Coins {
void GetNumCoins (int[] coinset, int biggercoin) {
int[] mincoins = new int[biggercoin+1];
Arrays.fill(mincoins, Integer.MAX_VALUE);
// 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.length; c++) {
if (val >= coinset[c]) {
mincoins[val] = Math.min (mincoins[val-coinset[c]] + 1, mincoins[val]);
}
}
}
int val = 0;
System.out.println ("Value | Minimum Coins");
for (int c : mincoins) {
System.out.println (val + " " + c);
val++;
}
System.out.println (mincoins[biggercoin] + " are needed to change value : " + biggercoin);
}
public static void main (String[] args) {
Coins c = new Coins();
int[] coinset = {1, 4, 9, 16};
int biggercoin = 10;
System.out.println ("Coin set");
for (int i : coinset)
System.out.print(i + " ");
System.out.println();
System.out.println("Coin to be changed :" + biggercoin);
c.GetNumCoins(coinset, biggercoin);
}
}
Output
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
© 2019-2026 Algotree.org | All rights reserved.
This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org
"The best error message is the one that never shows up. - Thomas Fuchs"