C/C++ program for greedy algorithm to find the minimum number of coins

The greedy algorithm is an algorithm used to find the optimal solution to a given problem. The greedy algorithm works by finding a local optimal solution for each part (the optimal solution to one part of the problem), thus showing that a global optimal solution can be found.

In this problem we will use the Greedy Algorithm algorithm to find the minimum number of coins/notes that can make up a given sum. For this we will consider all valid coins or banknotes, i.e. denominations { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}. We need to return the number of coins/notes needed to make up the sum.

Let us give a few examples to understand the context better -

Example 1 -

Input : 1231
Output : 7

Instructions - We need two 500 rupee notes , two 100 rupee notes, one 20 rupee note, one 10 rupee note and one Re 1 coin. The total is 2 2 1 1 1 = 7

Example 2 -

Input : 2150
Output : 3

Instructions - We need one Rs 2000 note, one Rs 100 note and one Rs 50 note.

To solve this problem using a greedy algorithm, we will find the largest denomination of banknotes that can be used. We will then subtract the maximum denomination from the sum and do the same process again until the sum is zero.

Algorithm

Input: sum,
Initialise the coins = 0
Step 1: Find the largest denomination that can be used i.e. smaller than sum.
Step 2: Add denomination two coins and subtract it from the Sum
Step 3: Repeat step 2 until the sum becomes 0.
Step 4: Print each value in coins.

Example

Real-time demonstration

#include <bits/stdc++.h>
using namespace std;
int notes[] = { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 };
int n = sizeof(notes) / sizeof(notes[0]);
void minchange(int sum){
   vector<int> coins;
   for (int i = n - 1; i >= 0; i--) {
      while (sum >= notes[i]) {
         sum -= notes[i];
         coins.push_back(notes[i]);
      }
   }
   for (int i = 0; i < coins.size(); i++)
      cout << coins[i] << "\t";
}
int main(){
   int n = 3253;
   cout << "The minimum number of coins/notes that sum up " << n << " is \t ";
   minchange(n);
   return 0;
}

Output

The minimum number of coins/notes that sum up 3253 is
2000 500 500 200 50 2 1

The above is the detailed content of C/C++ program for greedy algorithm to find the minimum number of coins. For more information, please follow other related articles on the PHP Chinese website!