De ce contează?
Casiera îți dă rest 28 de lei. Fără să se gândească mult, ea ia de fiecare dată bancnota cea mai mare care încape: o hârtie de 10, încă una de 10, apoi una de 5, apoi monede de 1. Niciodată nu calculează toate combinațiile posibile — la fiecare pas ia pur și simplu cea mai mare bucată care nu depășește restul. Asta este, în esență, strategia greedy: lacomă, grăbită, mereu cu ochii pe ce pare cel mai bun ACUM.
Ce este
O strategie greedy (lacomă) construiește răspunsul pas cu pas, iar la fiecare pas face alegerea care pare cea mai bună local — adică privind doar la momentul de față, fără să se uite înainte la consecințe. Speranța ei este că suma acestor alegeri locale bune dă răspunsul cel mai bun global.
E o metodă atractivă din două motive:
- E simplă — nu încerci toate variantele, iei mereu „cea mai bună de aici".
- E rapidă — de obicei o singură trecere prin date, fără să te întorci.
Dar tocmai aici e capcana: „cel mai bun acum" nu înseamnă mereu „cel mai bun la final". Uneori o alegere care pare modestă la pasul curent îți deschide drumul către un rezultat global mult mai bun.
Greedy = la fiecare pas, alegerea optimă local, fără să dai înapoi. Asta o face rapidă și ușor de scris — dar NU garantează optimul global. Pentru fiecare problemă trebuie să demonstrezi că lăcomia duce la răspunsul corect; altfel poate da un rezultat greșit care „pare" bun.