Informatică Programare
Algoritmi greedy exemple C++
Algoritmii greedy în C++ sunt strategii care iau decizii optime local la fiecare pas, sperând să ducă la o soluție globală optimă. Aceștia sunt eficienți și simpli, dar nu funcționează pentru toate problemele. Sunt folosiți în probleme precum schimbul de monede sau problema rucsacului fracționar.
Caracteristici ale algoritmilor greedy
- Alegere greedy La fiecare pas, alegi cea mai bună opțiune disponibilă fără a te gândi la consecințele viitoare.
- Optimalitate locală Decizia pare optimă în momentul luării ei; de exemplu, în problema schimbului, alegi cea mai mare monedă posibilă.
- Limitări Nu garantează soluția optimă pentru toate problemele; trebuie să demonstrezi că abordarea greedy funcționează pentru cazul specific.
Exemplu: Problema schimbului monedelor în C++
- 1 Pasul 1: Definire date Ai o sumă S de bani și un set de monede cu valori sortate descrescător, de exemplu {50, 10, 5, 1} lei.
- 2 Pasul 2: Inițializare Declari un vector pentru a stoca numărul de monede de fiecare tip și îl inițializezi cu 0.
- 3 Pasul 3: Aplicare greedy Parcurgi monedele în ordine descrescătoare; pentru fiecare monedă, cât timp S >= valoarea monedei, scazi valoarea din S și incrementezi numărul pentru acea monedă.
- 4 Pasul 4: Cod exemplu #include <iostream> #include <vector> using namespace std; int main() { int S = 123; vector<int> monede = {50, 10, 5, 1}; vector<int> numar(monede.size(), 0); for (int i = 0; i < monede.size(); i++) { while (S >= monede[i]) { S -= monede[i]; numar[i]++; } } for (int i = 0; i < monede.size(); i++) cout << monede[i] << ": " << numar[i] << endl; return 0; }
Testează algoritmul greedy pe mai multe seturi de date pentru a verifica dacă oferă întotdeauna soluția optimă.