Metoda Greedy (probleme de optimizare – planificare, schimb de monede)

Metoda Greedy (sau algoritmul lacom) este o tehnică de proiectare a algoritmilor utilizată pentru rezolvarea problemelor de optimizare. Principiul de bază este de a lua cea mai bună decizie la fiecare pas local, sperând că aceasta va duce la o soluție globală optimă. Nu există o revenire asupra deciziilor luate, ceea ce face algoritmul rapid, dar nu întotdeauna corect pentru toate problemele.

Pentru ca metoda Greedy să fie corectă, problema trebuie să aibă două proprietăți: (1) Substructura optimă – soluția optimă a problemei conține soluții optime ale subproblemelor; (2) Alegerea greedy (lacomă) – o alegere locală optimă conduce la o soluție globală optimă.

Exemplu clasic: Problema schimbului de monede (coin change). Se dă o sumă S și un set de monede (de exemplu, 1, 5, 10, 25 bani). Algoritmul greedy alege cea mai mare monedă care nu depășește suma rămasă, repetând până se atinge S. Pentru sistemul monedei americane (1, 5, 10, 25), greedy este optim, dar nu și pentru sisteme nestandard (ex: monede 1, 3, 4, suma 6 – greedy dă 4+1+1=3 monede, dar optimul este 3+3=2 monede).

Alt exemplu: Planificarea activităților (interval scheduling). Se dau N activități cu timpi de început și sfârșit și se dorește alegerea unui număr maxim de activități care nu se suprapun. Algoritmul greedy sortează activitățile după timpul de sfârșit și le selectează pe cele care nu se suprapun cu ultima aleasă. Acest algoritm este optim datorită alegerii greedy (cea care se termină cel mai devreme lasă mai mult loc pentru restul).

În rezumat, metoda Greedy se aplică cu succes problemelor de optimizare unde o alegere locală este suficientă, dar trebuie verificată optimalitatea în contextul dat, în special la bacalaureat, unde apar frecvent probleme de planificare și schimb de monede.

Exemple

• Exemplu 1: Planificare activități (BAC 2023, varianta 1). Se dau activitățile: A1(1,4), A2(3,5), A3(0,6), A4(5,7), A5(3,8), A6(5,9), A7(6,10), A8(8,11), A9(8,12), A10(2,13). Sortează după timpul de sfârșit: A1(1,4), A2(3,5), A4(5,7), A7(6,10), A8(8,11), A9(8,12), A10(2,13). Se selectează A1, apoi A4 (începe la 5 după 4), apoi A8 (începe la 8 după 7), etc. Rezultat: A1, A4, A8 – 3 activități. Verificare: nu se pot alege mai multe.
• Exemplu 2: Schimb de monede (BAC 2022). Se dă suma S=73, monede 1, 5, 10, 25. Greedy: 25+25+10+10+1+1+1 = 7 monede. Soluție optimă? Da, pentru acest sistem. Alt sistem: monede 1, 3, 4, S=6. Greedy: 4+1+1 = 3 monede. Optim: 3+3 = 2 monede. Atenție! Greedy nu e întotdeauna optimal.
• Exemplu 3: Problema rucsacului fracționar (Knapsack fracționar). Se dau obiecte cu greutate și profit, se poate lua o fracțiune. Algoritmul greedy sortează după raportul profit/greutate descrescător și alege cât mai mult din cel mai rentabil. De exemplu, obiecte: O1(profit 60, greutate 10, raport 6), O2(100,20,5), O3(120,30,4). Capacitate rucsac 50. Greedy: ia O1 întreg (10, profit 60), apoi O2 întreg (20, profit 100), apoi O3 doar 20 din 30 (profit 80). Profit total=240. Optimul fracționar este același, deoarece greedy dă optim pentru rucsac fracționar.

Concepte cheie: Alegerea locală optimă – se ia cea mai bună decizie la fiecare pas., Substructură optimă – soluția globală se bazează pe soluții optime ale subproblemelor., Problema planificării activităților – sortare după timpul de sfârșit., Problema schimbului de monede – greedy optim doar pentru sisteme canonice., Rucsac fracționar – raport profit/greutate ca criteriu de selecție.