Minimum Coin Change Problem

There is a list of coin C(c1, c2, ……Cn) is given and a value V is also given. Now the problem is to use the minimum number of coins to make the chance V.

Note − Assume there are an infinite number of coins C

In this problem, we will consider a set of different coins C{1, 2, 5, 10} are given, There is an infinite number of coins of each type. To make change the requested value we will try to take the minimum number of coins of any type.

As an example, for value 22 − we will choose {10, 10, 2}, 3 coins as the minimum.

The time complexity of this algorithm id O(V), where V is the value.

Input and Output

Input: A value, say 47 Output: Enter value: 47 Coins are: 10, 10, 10, 10, 5, 2

Algorithm

findMinCoin(value)

Input − The value to make the change

Output − Set of coins.

Begin    coins set with value {1, 2, 5, 10}    for all coins i as higher value to lower value do       while value >= coins[i] do          value := value – coins[i]          add coins[i], in thecoin list       done    done    print all entries in the coin list. End

Example

#include<iostream> #include<list> #define COINS 4 using namespace std; float coins[COINS] = {1, 2, 5, 10}; void findMinCoin(int cost) {    list<int> coinList;    for(int i = COINS-1; i>=0; i--) {       while(cost >= coins[i]) {          cost -= coins[i];          coinList.push_back(coins[i]); //add coin in the list       }    }    list<int>::iterator it;    for(it = coinList.begin(); it != coinList.end(); it++) {       cout << *it << ", ";    } } main() {    int val;    cout << "Enter value: ";    cin >> val;    cout << "Coins are: ";    findMinCoin(val);    cout << endl; }

Output

Enter value: 47 Coins are: 10, 10, 10, 10, 5, 2