C/C++-Programm für einen gierigen Algorithmus zum Ermitteln der Mindestanzahl an Münzen

Der Greedy-Algorithmus ist ein Algorithmus, der verwendet wird, um die optimale Lösung für ein bestimmtes Problem zu finden. Der Greedy-Algorithmus funktioniert, indem er für jeden Teil eine lokal optimale Lösung findet (die optimale Lösung für einen Teil des Problems) und zeigt so, dass eine globale optimale Lösung gefunden werden kann.

In diesem Problem verwenden wir den Greedy-Algorithmus, um die Mindestanzahl an Münzen/Banknoten zu ermitteln, die eine bestimmte Summe bilden können. Dabei berücksichtigen wir alle gültigen Münzen oder Banknoten, also die Stückelungen { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}. Wir müssen die Anzahl Münzen/Banknoten zurückgeben, die für die Summe erforderlich sind.

Lassen Sie uns ein paar Beispiele geben, um den Kontext besser zu verstehen –

Beispiel 1 –

Input : 1231
Output : 7

Erklärung – Wir benötigen zwei 500-Rupien-Scheine, zwei 100-Rupien-Scheine, einen 20-Rupien-Schein, einen 10-Rupien-Schein, Rupien-Banknoten und eine Re 1-Münze. Die Summe ist 2+2+1+1+1 = 7

Beispiel 2 –

Input : 2150
Output : 3

Anleitung – Wir benötigen einen 2000-Rs-Schein, einen 100-Rs-Schein und einen 50-Rs-Schein.

Um dieses Problem mithilfe eines Greedy-Algorithmus zu lösen, ermitteln wir die Banknote mit dem größten Nennwert, die verwendet werden kann. Anschließend subtrahieren wir den maximalen Nennwert von der Summe und wiederholen den gleichen Vorgang, bis die Summe Null ist.

Algorithmus

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.

Beispiel

Echtzeitdemonstration

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

Ausgabe

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

Das obige ist der detaillierte Inhalt vonC/C++-Programm für einen gierigen Algorithmus zum Ermitteln der Mindestanzahl an Münzen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!