Introducere în Greedy

Greedy (în română: „lacom”) e o paradigmă de rezolvare în care, la fiecare pas, alegem opțiunea care pare cea mai bună acum, fără a privi mai departe.

Sună prea simplu să meargă - și totuși, pentru o întreagă clasă de probleme, funcționează perfect. Pentru altele, eșuează spectaculos. Diferența între un programator care „simte” greedy și unul care nu, vine din multă practică și din a recunoaște tiparul.

Ce înseamnă „algoritm greedy”

Un algoritm greedy are mereu trei piese:

Stare: ce am construit până acum (o soluție parțială).
Alegere locală: dintre opțiunile disponibile, alegem una după un criteriu fix (cel mai mic, cel mai mare, cel mai aproape, cel mai scump, etc.).
Confirmare: opțiunea aleasă rămâne în soluție, nu o reconsiderăm mai târziu.

soluție = ∅
cât timp mai sunt opțiuni:
    aleg cea mai bună opțiune după criteriu
    o adaug în soluție
    elimin opțiunile incompatibile

Cheia: alegerile locale duc la optim global - dacă alegem mereu „cel mai bun acum”, la sfârșit avem cea mai bună soluție posibilă. Această proprietate se numește proprietatea de selecție greedy.

Când funcționează greedy?

Două condiții trebuie îndeplinite (greu de verificat, ușor de simțit cu experiența):

1. Substructură optimă

Soluția optimă a problemei conține soluții optime ale subproblemelor. (Această proprietate o au și algoritmii divide et impera și DP.)

2. Proprietatea de alegere greedy

Există o alegere locală optimă care face parte întotdeauna dintr-o soluție optimă globală.

Asta e partea grea. Trebuie demonstrată - fie matematic (prin exchange argument: dacă o soluție optimă nu conține alegerea greedy, putem schimba un element fără să o stricăm), fie empiric (prin teste pe cazuri mici).

Cum recunoști o problemă greedy?

Câteva semnale (nu garanții):

Enunțul cere maxim/minim ceva (cost minim, profit maxim, număr maxim de obiecte).
Există o resursă limitată care trebuie alocată inteligent.
Există o ordine naturală în input (timp, cost, dimensiune, raport).
Problema permite sortare după un criteriu și apoi parcurgere liniară.
N e suficient de mare încât DP cu multe stări nu încape (10⁵ - 10⁶).

Ce fac eu?

De obicei, dacă problema cere un optim (drum minim, cost minim, cel mai rapid etc.) atunci soluția cel mai probabil se bazează pe Greedy, DP sau Divide et Impera.

Acum trebuie să judecăm în funcție de enunț și de ce trebuie să calculăm (eu obișnuiesc să o iau prin eliminări). Din acest punct de vedere avem mai multe cazuri:

Problema se poate rezolva împărțind-o în mai multe subprobleme de același fel (asta elimină în cele mai multe cazuri Greedy):

dacă subproblemele sunt independente (nu se intersectează) → cel mai probabil Divide et Impera, dar nu elimină programarea dinamică;
dacă subproblemele se intersectează → cel mai probabil programare dinamică (DP).

Problema pare a fi Greedy, dar alegerea unui element curent e determinată de o restricție anterioară sau creează o restricție pentru următoarea alegere → cel mai probabil nu mai merge Greedy, ci e tot DP.

Pentru a mă asigura, caut contraexemple - cazuri în care Greedy ar da greșit.

Exchange argument - cum demonstrăm că greedy e corect

E cea mai folosită tehnică de demonstrație pentru greedy.

Idee: presupunem că soluția optimă OPT diferă de soluția greedy G. Identificăm primul punct unde diferă. Arătăm că putem schimba alegerea din OPT cu alegerea din G și soluția rămâne tot cel puțin la fel de bună. Repetăm - la sfârșit OPT devine G, deci G e tot optimă.

Exemplu de structură

Teoremă: alegerea greedy (cel mai mic deadline) duce la maximul de sarcini executate.

Demonstrație (schiță): Fie OPT o soluție optimă. Dacă prima alegere a lui OPT nu e cea greedy, putem înlocui prima sa sarcină cu cea greedy - rezultatul e tot valid și are același număr de sarcini. Repetăm pentru fiecare poziție.

În practică, NU scriem demonstrații în concursuri - dar gândirea ne ajută să vedem dacă greedy e corect înainte să-l implementăm.

Exemplu introductiv: distribuirea bomboanelor

Avem N copii așezați în șir, fiecare cu un scor s[i]. Vrem să dăm bomboane astfel încât:

Fiecare copil primește cel puțin 1 bomboană.

Dacă s[i] > s[i+1], atunci copilul i primește strict mai multe bomboane decât i+1.

Care e numărul minim de bomboane?

Idee greedy

Două parcurgeri:

Stânga → dreapta: dacă s[i] > s[i-1], atunci b[i] = b[i-1] + 1. Altfel b[i] = 1.
Dreapta → stânga: dacă s[i] > s[i+1], atunci b[i] = max(b[i], b[i+1] + 1).

Rezultat: suma b[i].

int n, s[NMAX], b[NMAX];

// Parcurgere stânga → dreapta
b[0] = 1;
for (int i = 1; i < n; i++) {
    if (s[i] > s[i-1]) {
        b[i] = b[i-1] + 1;
    } else {
        b[i] = 1;
    }
}

// Parcurgere dreapta → stânga
for (int i = n - 2; i >= 0; i--) {
    if (s[i] > s[i+1] && b[i] <= b[i+1]) {
        b[i] = b[i+1] + 1;
    }
}

long long total = 0;
for (int i = 0; i < n; i++) {
    total = total + b[i];
}

Complexitate: O(N).

De ce funcționează: fiecare copil primește exact cu unul mai mult decât maximul vecinilor săi mai mici. E alegerea minimă locală și se demonstrează că e și globală.

Capcane: când greedy NU funcționează

1. Restul cu monede non-canonice

Avem monede de 1, 6, 10. Cum dăm rest 12 cu minimum de monede?

Greedy: 10 + 1 + 1 = 3 monede.
Optim: 6 + 6 = 2 monede. Greedy greșește.

Explicație: setul {1, 6, 10} nu e „canonic” - alegerea celei mai mari monede întâi nu duce mereu la optim.

(Pentru sistemul european {1, 2, 5, 10, 20, 50, 100, ...}, greedy funcționează - de aceea e natural să credem că merge mereu.)

2. Rucsacul 0/1

N obiecte, fiecare cu greutate și valoare. Capacitate W. Maxim valoare?

Greedy după raport valoare/greutate eșuează:

Obiecte: (g=1, v=1), (g=2, v=4), (g=3, v=5)
W = 4

Greedy după raport: ia obiectul 1 (raport 1.0)… nu, ia obiectul 2 (raport 2.0) → 1 obiect, valoare 4. Restul de greutate 2 nu permite alt obiect (1 + 2 = 3 ≤ 4, dar adăugăm și obiectul 1 → 4+1=5).

Hm, greedy aici ar putea da 5. Dar pentru un caz mai rău:

Obiecte: (g=10, v=60), (g=20, v=100), (g=30, v=120)
W = 50

Greedy după raport: obiect 1 (6.0), apoi obiect 2 (5.0) → greutate 30, valoare 160.
Optim: obiect 2 + obiect 3 → greutate 50, valoare 220. Greedy greșește.

Pentru rucsac 0/1 e nevoie de DP, nu greedy. Doar rucsacul fracționar (poți tăia obiectele) merge cu greedy. Vezi Rucsacul fracționar.

3. Drumuri în grafuri

Drum minim de la A la B într-un graf cu costuri.

Greedy „mereu cel mai apropiat vecin” eșuează la grafuri cu cicluri și costuri inegale. Pentru asta există Dijkstra (care e tot greedy, dar cu o structură mai sofisticată - heap).

Strategii de gândire

Când vezi o problemă care „pare” greedy:

Identifică criteriul de sortare. După ce sortezi datele? (Cel mai mic? Cel mai mare? După raport?)
Încearcă pe un caz mic. Manual, cu hârtie. Dacă greedy obține optimul pentru N = 3, 4, 5, e probabil corect.
Caută contraexemple. Schimbă un input și vezi dacă greedy mai dă optim. Dacă găsești contraexemplu, greedy e greșit - caută DP sau altă abordare.
Gândește exchange argument. Dacă „intuitiv” simți de ce alegerea ta e cea mai bună, e un semn bun.

Lecțiile următoare

În acest capitol vei vedea probleme clasice greedy, fiecare cu:

Enunțul
Ideea greedy + intuiția
Demonstrația (informală)
Codul C++
Pas cu pas pe un exemplu concret
Capcanele frecvente

Lecția	Problemă	Pattern
Activity Selection	Selectare interviuri	Sortare după end time
Rest cu monede	Minim de monede	Sortare descrescătoare + când eșuează
Rucsacul fracționar	Rucsac unde poți tăia	Sortare după raport valoare/greutate

Greșeli frecvente

1. Aplicarea greedy fără verificare

„Pare greedy → scriu primul pattern care îmi vine în cap.” Probabil greșit. Mereu testează pe un caz mic înainte să te lansezi în implementare.

2. Sortare după criteriul greșit

Greedy = sortare + parcurgere. Sortarea după criteriu greșit (ex. începutul intervalului în loc de finalul) duce la rezultat suboptim.

3. Confuzia rucsac 0/1 vs fracționar

Fracționar (poți tăia) → greedy după raport.
0/1 (iei tot sau deloc) → DP.

4. Lipsa demonstrației pentru cazul critic

Pentru problemele rare, greedy nu funcționează. Mereu întreabă-te „de ce alegerea asta și nu alta?“. Dacă nu poți răspunde, șansa e mare să fie greșit.

5. Nu gândești la cazurile limită

N = 1, valori egale, ordine inversă, totul gol - greedy poate să crape pe cazuri marginale. Verifică.

Ce să reții

Greedy = la fiecare pas, alegerea locală optimă, fără a privi înapoi.
Funcționează când problema are substructură optimă + proprietatea de alegere greedy.
Demonstrația standard: exchange argument (înlocuire fără a strica optimul).
Sortare + parcurgere e șablonul cel mai des întâlnit.
Greedy eșuează la rucsac 0/1, drumuri într-un graf, monede non-canonice.
Practica e cheia - recunoști un greedy după ce ai văzut zeci.
Mereu testează pe un caz mic și caută contraexemple înainte să implementezi.

Probleme

pbinfoEasy Ssc→

pbinfoAlimentarea Masinii→

pbinfoModificaparanteze→

pbinfoSummax Xi→

pbinfoReactivi→

pbinfoYinyang→