# Minimum coins for a change

C++ : Minimum coins for changing a bigger coin using dynamic programming implemented in C++11

``````#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;

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
``````