Metoda Greedy

Ce este greedy

Greedy (lacom) = la fiecare pas, alegi cea mai buna optiune locala, fara a te intoarce si fara a tine cont de consecintele viitoare.

Nu garanteaza intotdeauna solutia optima globala — dar pentru anumite probleme este corecta si eficienta.

---

Structura generala

sorteaza datele dupa un criteriu relevant
pentru fiecare element (in ordine):
    daca poate fi inclus in solutie:
        include-l

---

Exemplu clasic: problema restului

Dai rest cu numar minim de monede dintr-un set de nominale date.

int nominale[] = {100, 50, 10, 5, 1};
int rest = 178, nrMonede = 0;

for (int i = 0; i < 5; i++) {
    nrMonede += rest / nominale[i];
    rest %= nominale[i];
}
cout << nrMonede;  // 7 (1x100 + 1x50 + 2x10 + 1x5 + 3x1)

Functioneaza corect pentru nominalele standard. Nu e optim pentru orice set de nominale.

---

Exemplu: programarea activitatilor

Se dau n activitati cu timp de start si sfarsit. Selecteaza cat mai multe activitati care nu se suprapun.

Strategie: sorteaza dupa timpul de sfarsit, alege activitatea care se termina cel mai devreme si nu se suprapune cu ultima aleasa.

struct Activitate { int start, sfarsit; };

bool cmp(Activitate a, Activitate b) {
    return a.sfarsit < b.sfarsit;
}

int main() {
    // ... citire n activitati in a[]
    sort(a, a + n, cmp);
    
    int cnt = 1, ultim = a[0].sfarsit;
    for (int i = 1; i < n; i++) {
        if (a[i].start >= ultim) {
            cnt++;
            ultim = a[i].sfarsit;
        }
    }
    cout << cnt;
}

---

Exemplu: rucsac fractionar

Se dau obiecte cu greutate si valoare. Rucsacul are capacitate maxima G. Poti lua fractiuni din obiecte.

Strategie: sorteaza dupa valoare/greutate descrescator, ia cat poti din fiecare.

sort(obiecte, ..., dupa valoare/greutate descrescator);
double valoareTotala = 0;
double capacitateRamasa = G;

for (auto& obj : obiecte) {
    if (obj.greutate <= capacitateRamasa) {
        valoareTotala += obj.valoare;
        capacitateRamasa -= obj.greutate;
    } else {
        valoareTotala += obj.valoare * (capacitateRamasa / obj.greutate);
        break;
    }
}

---

Cand functioneaza greedy

Greedy da solutia optima cand problema are:

• Proprietatea de substructura optima: solutia optima globala contine solutii optime pentru subprobleme
• Proprietatea de alegere greedy: exista o alegere locala optima care face parte din solutia globala optima

---

Greedy vs. Backtracking vs. Programare dinamica

	Greedy	Backtracking	Prog. dinamica
Intoarcere	Nu	Da	Nu
Optimalitate	Nu intotdeauna	Da	Da
Viteza	Rapid	Lent	Mediu

---

La examen

• Daca subiectul cere „numar minim/maxim” si datele pot fi sortate → gandeste greedy
• Justifica alegerea: de ce optiunea locala duce la optimul global?
• Daca greedy nu functioneaza → incearca programare dinamica