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,
C++ Minimum number of coins for changing a bigger coin.
#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