Programme C/C++ pour un algorithme glouton pour trouver le nombre minimum de pièces

L'algorithme glouton est un algorithme utilisé pour trouver la solution optimale à un problème donné. L'algorithme glouton fonctionne en trouvant une solution optimale locale pour chaque partie (la solution optimale à une partie du problème), montrant ainsi qu'une solution optimale globale peut être trouvée.

Dans ce problème, nous utiliserons l'algorithme Greedy Algorithm pour trouver le nombre minimum de pièces/billets pouvant constituer une somme donnée. Pour cela, nous considérerons toutes les pièces ou billets valides, c'est-à-dire les coupures { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000}. Nous devons renvoyer le nombre de pièces/billets nécessaires pour constituer la somme.

Donnons quelques exemples pour mieux comprendre le contexte -

Exemple 1 -

Input : 1231
Output : 7

Explication - Nous avons besoin de deux billets de 500 roupies, de deux billets de 100 roupies, d'un billet de 20 roupies, d'un billet de 10 roupies. une pièce Re 1. Le total est de 2+2+1+1+1 = 7

Exemple 2 -

Input : 2150
Output : 3

Instructions - Nous avons besoin d'un billet de Rs 2000, d'un billet de Rs 100 et d'un billet de Rs 50.

Pour résoudre ce problème à l'aide d'un algorithme glouton, nous trouverons la plus grosse coupure pouvant être utilisée. Nous soustrairons ensuite la dénomination maximale de la somme et recommencerons le même processus jusqu'à ce que la somme soit nulle.

Algorithme

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.

Exemple

Démonstration en temps réel

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

Sortie

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!