Ce vei învăța astăzi?
După această lecție vei înțelege principiul metodei Greedy („lăcomia"): la fiecare pas alegem cea mai bună opțiune locală, sperând că alegerea ne va duce la soluția optimă globală.
Ce este metoda Greedy?
Definiție: Metoda Greedy construiește o soluție pas cu pas: la fiecare pas alege varianta care pare cea mai bună în acel moment (optim local), fără să țină cont de consecințele viitoare și fără să mai revină asupra alegerii făcute.
Analogie: alegerea celui mai ieftin produs
Ai o listă de produse cu prețuri și vrei să cumperi un singur produs, cât mai ieftin. Parcurgi lista și, la fiecare produs, te întrebi: „este mai ieftin decât cel mai ieftin găsit până acum?" Dacă da, îl reții. La final rămâi cu cel mai ieftin produs, fără să fie nevoie să te răzgândești.
- La fiecare pas alegem varianta locală cea mai bună
- Reținem cea mai bună alegere de până acum
- La final, alegerea locală a produs optimul global
Caracteristicile metodei
Metoda Greedy se aplică atunci când o problemă are substructură optimală (soluția optimă conține soluții optime pentru subprobleme) și când alegerea greedy locală duce întotdeauna la soluția globală optimă.
| Greedy | Divide et impera |
|---|---|
| Alege pas cu pas optimul local | Descompune problema în subprobleme |
| Nu reconsideră deciziile luate | Rezolvă fiecare subproblemă separat |
| Construiește soluția progresiv | Combină rezultatele subproblemelor |
| Exemplu: cel mai ieftin produs | Exemplu: suma unui interval |
Important: nu toate problemele se rezolvă greedy! Dacă alegerea locală optimă nu garantează soluția globală optimă, metoda nu se aplică.
Primul program: cel mai ieftin produs
Citim n prețuri. Păstrăm în variabila minim cel mai mic preț întâlnit; la fiecare pas, dacă prețul curent este mai mic, îl actualizăm pe minim.
#include <iostream>
using namespace std;
int main() {
int n, pret, minim;
cin >> n;
cin >> minim;
for (int i = 2; i <= n; i++) {
cin >> pret;
if (pret < minim) {
minim = pret;
}
}
cout << minim << endl;
return 0;
}
Ce învățăm: la fiecare pas alegem cea mai bună variantă locală (cel mai mic preț de până acum); la final, alegerea locală coincide cu minimul global.
Exercițiu de completare
Completează descrierea metodei Greedy:
Metoda Greedy alege la fiecare pas ______ local, fără a mai ______ asupra deciziilor. Speranța este ca alegerea locală să ducă la soluția ______ optimă.
Bancă de cuvinte:
Exercițiu de completare: codul
Completează descrierea algoritmului pentru cel mai ieftin produs:
Inițializăm ______ul cu primul preț; pentru fiecare preț, dacă este mai ______, îl ______. La final afișăm valoarea reținută.
Bancă de cuvinte:
Test de înțelegere
Test rapid - metoda Greedy:
1. Metoda Greedy alege la fiecare pas optimul la nivel:
2. În metoda Greedy, deciziile luate:
3. Un exemplu de problemă rezolvabilă greedy este:
Aprofundare
Proprietatea de substructură optimală: metoda Greedy nu dă întotdeauna soluția optimă globală; ea funcționează doar când problema are substructură optimală, adică atunci când o alegere locală bună nu strică alegerile viitoare. De aceea, înainte de a aplica Greedy, trebuie să te întrebi: „dacă aleg acum optimul local, pot obține oricum optimul global?" Dacă răspunsul este da, metoda este corectă; altfel, trebuie altă abordare.
Când Greedy eșuează: un exemplu clasic este sistemul de monede 1, 3, 4 pentru restul 6. Greedy alege 4 + 1 + 1 (trei monede), dar soluția optimă este 3 + 3 (două monede). De aceea problema monedelor funcționează greedy doar pentru sisteme „canonice" de monede, cum este cel folosit la ora 6.
Optimul local, definit precis: „optimul local" nu înseamnă doar „cea mai mare valoare"; el depinde de criteriul problemei. La spectacole, alegerea greedy este spectacolul care se termină cel mai devreme; la rucsacul fracționar, obiectul cu cea mai mare eficiență valoare/greutate. Identificarea corectă a criteriului este jumătate din rezolvarea problemei.
De ce nu se reconsideră deciziile: odată aleasă, o decizie greedy este definitivă. Acesta este punctul care o deosebește de programarea dinamică, unde o decizie poate fi corectată implicit prin compararea soluțiilor parțiale. Dacă după câțiva pași constați că alegerea făcută pare greșită, înseamnă că problema nu se potrivește metodei.
Exemplu din viața reală: un programator care vrea să-și încarce laptopul cât mai repede alege întotdeauna încărcătorul deja conectat (optim local: timp zero de pregătire), fără să reconsidere decizia. Un bucătar care taie cea mai mare felie de tort o dată ce a început nu o mai pune la loc. Astfel de decizii „fără întoarcere" sunt esența metodei Greedy.
PbInfo - Cel mai ieftin produs
Enunț:
Cerință: Se citesc n prețuri, în lei. Să se afișeze prețul cel mai mic, folosind metoda Greedy (alegerea locală optimă la fiecare pas).
Date de intrare:
Programul citește n, apoi cele n prețuri, separate prin spații.
Date de ieșire:
Programul va afișa prețul minim.
Restricții și precizări:
1 ≤ n ≤ 100000; prețurile sunt numere naturale.
Exemplu:
Intrare:
4 15 8 12 6
Ieșire:
6
Cum gândim soluția:
- Citim primul preț în
minim - Pentru fiecare preț citit, dacă este mai mic decât
minim, îl actualizăm - Afișăm
minim
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int n, pret, minim;
cin >> n;
cin >> minim;
for (int i = 2; i <= n; i++) {
cin >> pret;
if (pret < minim) {
minim = pret;
}
}
cout << minim << endl;
return 0;
}
Ce învățăm: alegerea locală (cel mai mic preț de până acum) conduce la optimul global, fără a fi nevoie să reconsiderăm prețurile deja citite.
PbInfo - Suma maximă (greedy)
Enunț:
Cerință: Se citesc n numere naturale și un număr k. Să se afișeze suma maximă pe care o putem obține alegând k dintre numere.
Date de intrare:
Programul citește n, k, apoi cele n numere.
Date de ieșire:
Programul va afișa suma maximă obținută cu k numere.
Restricții și precizări:
1 ≤ k ≤ n ≤ 1000; strategia greedy: alegem întotdeauna cele mai mari valori.
Exemplu:
Intrare:
5 3 4 9 2 7 5
Ieșire:
21
Cum gândim soluția:
- Sortăm numerele descrescător
- Alegem primele k numere (cele mai mari)
- Calculăm și afișăm suma lor
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int v[1001];
void sorteaza(int n) {
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (v[i] < v[j]) {
int aux = v[i];
v[i] = v[j];
v[j] = aux;
}
}
}
}
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
sorteaza(n);
int s = 0;
for (int i = 1; i <= k; i++) {
s += v[i];
}
cout << s << endl;
return 0;
}
Ce învățăm: alegerea greedy (cele mai mari k valori) dă suma maximă; după sortare descrescătoare, luăm primele k elemente.
Exercițiul Practic: primele alegeri greedy
Sarcini de lucru
Rezolvă sarcinile de mai jos pentru a exersa alegerea locală optimă
Sarcina 1: Minimul și poziția sa
Cerință: Se citesc n prețuri. Afișează prețul minim și poziția (numărul de ordine) la care apare. Dacă minimul apare de mai multe ori, afișează prima poziție.
Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;
int main() {
int n, pret, minim, poz, i;
cin >> n;
cin >> minim;
poz = 1;
for (i = 2; i <= n; i++) {
cin >> pret;
if (pret < minim) {
minim = pret;
poz = i;
}
}
cout << minim << " " << poz << endl;
return 0;
}
Verifică: pentru prețurile 8 3 5 3 1, minimul este 1 la poziția 5, deci afișăm 1 5. Folosim < strict, deci prima poziție a minimului este reținută.
Sarcina 2: Suma primelor k valori după sortare descrescătoare
Cerință: Se citesc n numere și un număr k. Afișează suma celor mai mari k numere, sortând descrescător și adunând primele k.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int v[1001];
void sorteaza(int n) {
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (v[i] < v[j]) {
int aux = v[i];
v[i] = v[j];
v[j] = aux;
}
}
}
}
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
sorteaza(n);
int s = 0;
for (int i = 1; i <= k; i++) {
s += v[i];
}
cout << s << endl;
return 0;
}
Verifică: pentru n = 5, k = 2 și numerele 4 9 2 7 5, sortăm descrescător (9 7 5 4 2) și adunăm primele 2: 9 + 7 = 16.
Scrie pe caiet - Metoda Greedy
Titlul lecției
- Ora 5: Metoda Greedy - caracteristici
Definiția lecției
Metoda Greedy construiește soluția unei probleme pas cu pas, alegând la fiecare pas optimul local — cea mai bună variantă în momentul respectiv — fără a reconsidera deciziile deja luate. Spre deosebire de Divide et impera, care descompune și combină recursiv, Greedy merge secvențial, de regulă iterativ. Metoda se aplică doar problemelor cu substructură optimală (proprietatea că alegerea locală optimă conduce la soluția globală optimă); altfel rezultatul poate fi greșit. Pasul critic este fixarea criteriului de alegere (cel mai ieftin produs, cea mai mare monedă, ora de sfârșit cea mai devreme). Programul de bază al lecției determină minimul unei liste de prețuri, cu o singură buclă și o comparație, model pentru toate problemele greedy din modul.
Definiții esențiale
- Metoda Greedy: metodă de programare în care soluția se construiește pas cu pas, alegând la fiecare pas optimul local, fără a reconsidera deciziile deja luate.
- Optim local: cea mai bună alegere posibilă la pasul curent, conform unui criteriu bine definit al problemei.
- Substructură optimală: proprietatea problemei care garantează că alegerea optimului local la fiecare pas conduce la soluția globală optimă; fără ea, Greedy nu este corectă.
- Diferența față de D&I: Greedy construiește soluția secvențial, iterativ, pe când Divide et impera descompune și combină recursiv.
Algoritmul cheie - pseudocod
- Schema Greedy: inițializează soluția → repetă: alege optimul local → actualizează soluția → până când problema este rezolvată.
- Exemplu (cel mai ieftin produs):
minim = pret[1]; pentru fiecare preț următor, dacă e mai mic, actualizeazăminim.
Algoritmul cheie - cod C++
int n, pret, minim; cin >> n; cin >> minim;- Bucla
for (int i = 2; i <= n; i++)cuif (pret < minim) minim = pret; - Afișează
minim.
Greșeli comune de evitat
- Aplicarea Greedy fără a verifica existența substructurii optimale: rezultatul poate să nu fie optimul global.
- Definirea greșită a criteriului de alegere (de exemplu, cea mai mare valoare în loc de cea mai bună eficiență).
- Reconsiderarea deciziilor după un pas: dacă „te întorci", nu mai ești în Greedy.
- Inițializarea greșită a variabilei de soluție (de exemplu, minimul pornit de la 0).
Sfaturi practice și trucuri
- Înainte de implementare, răspunde la două întrebări: care este criteriul local și de ce alegerea locală nu strică soluția globală?
- Testează mereu pe un exemplu în care greedy pare „prea bun ca să fie adevărat": s-ar putea să găsești un contraexemplu.
- La oral, formulează justificarea: „la fiecare pas am ales optimul local și problema are substructură optimală, deci soluția este optimă".
- Recunoaște problemele tipice Greedy: monede, spectacole, rucsac fracționar, platou, minimul de resurse.
Exemplu practic
Un elev are un buget limitat și vrea să cumpere cel mai ieftin dintre n manuale, ca să-i rămână cât mai mulți bani. Parcurge lista de prețuri și reține de fiecare dată prețul mai mic, fără să se răzgândească — exact algoritmul greedy de mai jos:
int n, pret, minim;
cin >> n;
cin >> minim;
for (int i = 2; i <= n; i++) {
cin >> pret;
if (pret < minim) {
minim = pret;
}
}
cout << minim << endl;