De ce contează?
Cobori un munte pe ceață și vrei la vale cât mai repede. Strategia simplă: la fiecare pas mergi în direcția care coboară cel mai abrupt. De multe ori ajungi jos — dar uneori nimerești o groapă din care nu mai cobori. Asta e metoda Greedy: alegi ce e mai bun acum, sperând că e bine și la final.
Ideea: optimul local la fiecare pas
Metoda Greedy (lacomă) construiește soluția pas cu pas, alegând de fiecare dată opțiunea care pare cea mai bună în acel moment, fără să revină asupra deciziilor. E simplă și rapidă — dar corectă doar pentru anumite probleme.
Exemplu clasic: restul cu monede
Dai rest de R lei cu monede de 1, 5, 10, 50. Greedy: la fiecare pas iei cea mai mare
monedă care încape în restul rămas.
Algoritm pas cu pas: rest de 67 lei
| pas | rest rămas | monedă luată |
|---|---|---|
| 1 | 67 | 50 |
| 2 | 17 | 10 |
| 3 | 7 | 5 |
| 4 | 2 | 1 |
| 5 | 1 | 1 |
Total: 5 monede (50 + 10 + 5 + 1 + 1). Pe sistemul românesc, Greedy dă numărul minim.
Implementare C++
#include <iostream>
using namespace std;
int main() {
int monede[] = {50, 10, 5, 1}; // descrescator
int R;
cin >> R;
int total = 0;
for (int i = 0; i < 4; i++) {
while (R >= monede[i]) { // luam cat putem din moneda curenta
R -= monede[i];
total++;
}
}
cout << total << " monede\n"; // 67 -> 5
return 0;
}Greedy nu „încearcă" variante — ia decizia și merge mai departe. De aceea e rapid (O(n) adesea). Prețul: trebuie să fii sigur că alegerea locală e și global optimă.
Când Greedy GREȘEȘTE
Schimbă monedele în și dă rest de 6. Greedy ia 4 + 1 + 1 = 3 monede. Dar optimul e 3 + 3 = 2 monede. Alegerea locală (cea mai mare monedă) a ratat soluția globală.
Acesta e pericolul central: Greedy e corect doar pentru anumite structuri de problemă. Pe sistemele „canonice" de monede funcționează; pe altele, nu. Mereu trebuie justificat că strategia lacomă duce la optim (vezi lecția-punte).
Când să te gândești la Greedy
- Poți defini clar „cea mai bună alegere de moment"?
- Alegerea de acum nu strică opțiunile viitoare?
- Adesea ajută o sortare prealabilă (tema următoare): procesezi elementele într-o ordine deșteaptă.
Complexitate
| Tip | Timp tipic | Spațiu |
|---|---|---|
| Greedy simplu | O(n) | O(1) |
| Greedy cu sortare | O(n log n) | O(1) |
Capcane reale la metoda Greedy:
- Presupui că Greedy e mereu corect: pe multe probleme (rucsac 0/1, monede necanonice) ratează optimul. Verifică sau demonstrează.
- Alegere locală greșită: definești prost „cea mai bună de moment" → soluție suboptimă chiar și unde Greedy ar fi mers.
- Nu sortezi când trebuie: multe probleme Greedy cer o ordine prealabilă; fără ea, alegerea lacomă n-are sens.
- Confuzi cu programare dinamică: când alegerile se influențează reciproc, Greedy nu ajunge — ai nevoie de DP.
De reținut
- Greedy = la fiecare pas alegi optimul local, fără să revii; rapid, dar nu mereu corect.
- Funcționează pe structuri „canonice" (ex. rest cu monede românești); pe altele ratează optimul.
- Justifică mereu corectitudinea; adesea o sortare prealabilă face alegerea lacomă validă.