Casierul care-ți dă restul nu calculează toate combinațiile posibile — ia mereu cea mai mare bancnotă care încape. Alegere local optimă, la fiecare pas, fără să se mai întoarcă. Asta e Greedy: rapidă, elegantă… și uneori înșelătoare.
Multe probleme cer un optim — cel mai mult, cel mai puțin, cel mai scurt. Greedy le atacă mergând înainte și luând, la fiecare pas, cea mai bună alegere de moment.
Dintr-o mulțime de numere întregi, alege o submulțime cu suma cât mai mare. Pe care le iei?
Încerci TOATE submulțimile și o reții pe cea cu suma maximă. Pentru n numere sunt 2ⁿ submulțimi → O(2ⁿ). La n = 40 deja e imposibil în timp rezonabil.
O singură parcurgere: iei tot ce e pozitiv, ignori restul → O(n). Și e ușor de justificat: orice pozitiv adăugat crește suma, orice negativ ar micșora-o.
Bancnote de 50, 10, 5 și 1 leu. Strategia: mereu cea mai mare care încape. Tastează un rest:
La un ghișeu stau n persoane, fiecare cu un timp de servire. Fiecare așteaptă până sunt servite toate din fața ei. În ce ordine le așezăm ca media timpilor de așteptare să fie minimă?
Timpii de servire: 7, 6, 3, 10, 6, 3. Timpul de așteptare al fiecărei persoane = suma timpilor de servire ale celor din fața ei + al ei.
Mai multe spectacole, o singură scenă. Vrem CÂT MAI MULTE, fără suprapuneri. Criteriul lacom câștigător: cel care se TERMINĂ primul.
| Criteriu lacom | Verdict | De ce |
|---|---|---|
| după durată (cel mai scurt întâi) | ✗ greșit | un spectacol scurt la mijloc poate bloca două lungi care NU se suprapun între ele |
| după ora de început | ✗ greșit | unul care începe devreme, dar ține mult, îți fură toată scena |
| după ora de final | ✓ corect | cine termină primul eliberează scena cel mai devreme → loc maxim pentru rest |
Acum vrem să programăm TOATE spectacolele, nu doar câteva. De câte săli avem nevoie, la minim, ca nimic să nu se suprapună?
Un rucsac duce cel mult Gmax kg. Fiecare obiect are o greutate și un câștig. Ce încarci ca să obții câștig maxim? Cheia lacomă: eficiența = câștig / greutate.
Gmax = 10. Obiectele (deja sortate descrescător după eficiență):
Obiectele NU se pot tăia — iei un obiect întreg doar dacă mai încape. Aici: 4, 2, 1 (greutate 6, câștig 19). Obiectul 3 (8 kg) nu mai încape.
Obiectele SE pot tăia — umpli restul cu o fracțiune. Aici: 4, 2, 1 + ½ din obiectul 3 (mai încap 4 kg din 8) → câștig 19 + 4 = 23, rucsac plin.
Greedy nu garantează mereu optimul. O monedă exotică e de-ajuns ca să-l păcălească:
Lacomul ia 4 (cea mai mare!) și se blochează în mărunțiș. Alegerea local optimă NU a dus la optimul global.
Sistemul monetar real e construit special: fiecare bancnotă e „acoperită" de cele mai mici (50 = 5×10, 10 = 2×5, 5 = 5×1). La astfel de sisteme, lăcomia chiar E optimă. Morala BAC: Greedy se folosește când poți JUSTIFICA de ce alegerea locală nu strică viitorul — altfel, contraexemplul te așteaptă.
Opt întrebări despre metoda Greedy și problemele ei clasice.
De la mână la tastatură — de la ★ (pe hârtie) la ★★★ (cu demonstrație).
| # | Cerință | Nivel |
|---|---|---|
| 1 | Pentru Gmax = 15 și obiectele g = (4, 5, 6, 3), c = (10, 20, 18, 9): calculează eficiențele, apoi rezolvă varianta discretă și continuă. | ★ |
| 2 | Implementează în C++ varianta discretă: structură cu (greutate, profit, nr, ales), sortare descrescătoare după eficiență, umplere cât încape. | ★★ |
| 3 | Extinde la varianta continuă: după ce nu mai încape un obiect întreg, adaugă fracțiunea din el care umple exact rucsacul. | ★★ |
| # | Cerință | Nivel |
|---|---|---|
| 4 | Timpi de servire 4, 2, 8, 1, 7: găsește ordinea care minimizează timpul mediu de așteptare și calculează-l. | ★ |
| 5 | Se dau 6 intervale de spectacole. Determină numărul maxim care încap într-o singură sală (sortare după final). | ★★ |
| 6 | Aceleași 6 intervale: câte săli minim sunt necesare ca să încapă TOATE? (sortare după început, adâncime). | ★★ |
| 7 | Găsește un sistem de monede și o sumă pentru care greedy dă un răspuns neoptim. Demonstrează cu numere. | ★★★ |
Metoda Greedy, condensată.