Greedy Algorithm to find Minimum number of Coins

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.

So the problem is stated as we have been given a value V, if we want to make change for V Rs, and we have infinite supply of { 1, 2, 5, 10, 20} valued coins, what is the minimum number of coins and/or notes needed to make the change?

Solution: The idea is simple Greedy Algorithm. Start from largest possible denomination and keep adding denominations while remaining value is greater than 0.

1) Initialize result as empty.
2) Find the largest denomination that is smaller than V.
3) Add found denomination to result. Subtract value of found denomination from V.
4) If V becomes 0, then print result.
Else repeat steps 2 and 3 for new value of V

Examples:

Input: V = 70
Output: 5
We need 4 20 Rs coin and a 10 Rs coin.

Input: V = 7
Output: 3
We need a 10 Rs coin, a 5 Rs coin and a
2 Rs coin.

C++ program

#include <iostream>
using namespace std;

int deno[] = { 1, 2, 5, 10, 20};
int n = sizeof(deno) / sizeof(deno[0]);

void findMin(int V)
{

{
for (int i= 0; i < n-1; i++) {
for (int j= 0; j < n-i-1; j++){
if (deno[j] > deno[j+1])
swap(&deno[j], &deno[j+1]);
}

int ans[V];
for (int i = 0; i <n; i++) {
while (V >= deno[i]) {
V -= deno[i];
ans[i]=deno[i];
}
}

for (int i = 0; i < ans.size(); i++)
cout << ans[i] << “ “;
}

// Main Program
int main()
{
int a;
cout<<”Enter you amount “;
cin>>a;
cout << “Following is minimal number of change for “ << a<< “ is “;
findMin(a);
return 0;
}

Output:

Enter you amount: 70
Following is minimal number of change for 70: 20 20 20 10

Time complexity of the greedy coin change algorithm will be:

1. For sorting n coins O(nlogn).
2. While loop, the worst case is O(total). If all we have is the coin with 1-denomination.
3. Complexity for coin change problem becomes O(n log n) + O(total).