Metoda greedy

Numele vine din limba engleză și înseamnă „lacom”: algoritmul ia de fiecare dată cel mai bun câștig imediat. Această strategie nu este corectă pentru orice problemă. Trebuie demonstrat că alegerile locale conduc la o soluție globală optimă.

Ideea metodei

O problemă potrivită pentru greedy are, în general, următoarele componente:

• o mulțime de obiecte sau de alegeri posibile;
• o soluție construită treptat;
• o condiție de fezabilitate, care arată dacă alegerea păstrează soluția validă;
• un criteriu de selecție, care stabilește ce alegere este cea mai bună acum;
• un criteriu de oprire, când soluția este completă sau nu mai există alegeri.

Schema generală este:

soluție ← ∅
cât timp soluția nu este completă și mai există candidați:
    alege cel mai bun candidat după criteriul greedy
    elimină candidatul din mulțimea candidaților
    dacă adăugarea lui păstrează fezabilitatea:
        adaugă candidatul în soluție
returnează soluția

Când este oportună metoda greedy

Metoda greedy este potrivită atunci când se pot verifica două proprietăți:

Dacă nu poate fi justificată măcar prima proprietate, alegerea „celei mai bune acum” este doar o euristică. Ea poate produce o soluție validă, dar nu neapărat optimă.

Proiectarea unui algoritm greedy

Înainte de scrierea programului, se răspunde la întrebările:

1. Care sunt candidații?
2. După ce criteriu se ordonează sau se alege un candidat?
3. Ce înseamnă că alegerea este admisibilă?
4. Ce stare trebuie păstrată după fiecare alegere?
5. De ce nu va fi nevoie de revenirea asupra unei alegeri făcute?
6. Când se oprește algoritmul?

De multe ori, algoritmul are doi pași:

1. sortarea candidaților după criteriul greedy;
2. parcurgerea în această ordine, cu acceptarea candidaților care respectă condiția problemei.

Dacă sortarea domină prelucrarea, timpul total este de regulă O(n log n). Dacă obiectele sunt deja ordonate, parcurgerea poate fi O(n).

Problema rucsacului în varianta continuă

Enunțul problemei

Un depozit trebuie golit, iar camionul care îl preia poate transporta cel mult Gmax kilograme. În depozit se află n mărfuri vrac, de exemplu făină, zahăr sau orez, fiecare cu greutatea ei și cu profitul pe care îl aduce.

Mărfurile sunt vrac, deci dintr-un sac se poate lua și numai o parte, iar profitul obținut este proporțional: jumătate de sac de făină aduce jumătate din profitul sacului.

Se cere profitul maxim care poate fi încărcat în camion.

Formal, se dau n obiecte; obiectul i are greutate și profitTotal, iar rucsacul are capacitatea Gmax. Din fiecare obiect se poate lua o fracțiune, iar profitul obținut este proporțional cu fracțiunea luată. Se cere profitMaxim, adică profitul total cel mai mare.

Date de intrare. Pe prima linie, capacitatea Gmax. Pe a doua, numărul n de obiecte. Pe fiecare dintre următoarele n linii, denumirea, greutatea și profitul total al unui obiect.

Date de ieșire. Profitul maxim care încape în rucsac.

Ideea de rezolvare

Pentru fiecare obiect se calculează cât profit aduce un kilogram din el:

profitKg = profitTotal / greutate

La obiectul A din exemplul de mai jos, 60 / 10 = 6: fiecare kilogram încărcat din A aduce un profit de 6. Numărul acesta se mai numește valoarea pe unitatea de greutate sau eficiența obiectului.

Criteriul greedy este ordonarea descrescătoare după profitKg. Astfel, în rucsac intră mai întâi kilogramele care aduc cel mai mult.

Algoritmul

1. Se calculează profitKg pentru fiecare obiect.
2. Obiectele se ordonează descrescător după profitKg.
3. Obiectele se parcurg în această ordine, cât timp mai există loc.
4. Dacă obiectul încape integral, se ia întreg, iar greutatea lui se scade din Gmax.
5. Altfel, se ia doar fracțiunea care mai încape, la profit se adaugă profitKg · Gmax, iar Gmax devine zero, deoarece rucsacul s-a umplut.

Schema logică

Din desen se vede că nicio săgeată nu duce înapoi la blocul de sortare: după ce un obiect a fost luat, algoritmul nu revine asupra alegerii.

Gmax nu păstrează capacitatea citită, ci cât loc a mai rămas: din el se scade greutatea fiecărui obiect luat întreg. Pe ramura în care obiectul nu mai încape, Gmax devine zero, condiția Gmax > 0 este falsă la următoarea verificare, iar structura repetitivă se încheie. Ultimul obiect luat este singurul luat parțial.

Exemplu

Capacitatea rucsacului este 50 kg:

50
3
A 10 60
B 20 100
C 30 120

Se iau A și B, pentru o greutate de 30 kg și un profit de 160. Mai rămân 20 kg, deci se iau 20/30 din C, cu profitul 20 · 4 = 80. Profitul maxim este 240, iar programul scrie 240.

citește Gmax, n și cele n obiecte
pentru fiecare obiect:
    profitKg ← profitTotal / greutate

sortează obiectele descrescător după profitKg

profitMaxim ← 0
pentru i ← 1, n, cât timp Gmax > 0:
    dacă ob[i].greutate ≤ Gmax:
        profitMaxim ← profitMaxim + ob[i].profitTotal
        Gmax ← Gmax - ob[i].greutate
    altfel:
        profitMaxim ← profitMaxim + ob[i].profitKg * Gmax
        Gmax ← 0

scrie profitMaxim

#include <iostream>
using namespace std;

const int MAX = 101;

struct obiect {
    char denumire[20];
    float greutate, profitTotal, profitKg;
} ob[MAX];

int n, k;
float Gmax;
obiect sol[MAX];
float profitMaxim = 0;

void citire() {
    cin >> Gmax >> n;
    for (int i = 1; i <= n; i++) {
        cin >> ob[i].denumire
           >> ob[i].greutate >> ob[i].profitTotal;
        ob[i].profitKg = ob[i].profitTotal / ob[i].greutate;
    }
}

void sortare() {
    obiect aux;
    for (int i = 1; i <= n - 1; i++)
        for (int j = i + 1; j <= n; j++)
            if (ob[i].profitKg < ob[j].profitKg) {
                aux = ob[i];
                ob[i] = ob[j];
                ob[j] = aux;
            }
}

void greedy() {
    k = 1;
    for (int i = 1; i <= n && Gmax > 0; i++)
        if (ob[i].greutate <= Gmax) {
            sol[k++] = ob[i];
            profitMaxim = profitMaxim + ob[i].profitTotal;
            Gmax = Gmax - ob[i].greutate;
        } else {
            sol[k] = ob[i];
            sol[k].greutate = Gmax;
            sol[k].profitTotal = ob[i].profitKg * Gmax;
            profitMaxim = profitMaxim + ob[i].profitKg * Gmax;
            k++;
            Gmax = 0;
        }
}

void afisare() {
    cout << profitMaxim;
}

int main() {
    citire();
    sortare();
    greedy();
    afisare();
}

def citire():
    Gmax = float(input())
    n = int(input())
    ob = []
    for _ in range(n):
        denumire, greutate, profitTotal = input().split()
        greutate = float(greutate)
        profitTotal = float(profitTotal)
        ob.append({
            "denumire": denumire,
            "greutate": greutate,
            "profitTotal": profitTotal,
            "profitKg": profitTotal / greutate
        })
    return Gmax, ob


def sortare(ob):
    return sorted(ob, key=lambda o: o["profitKg"], reverse=True)


def greedy(Gmax, ob):
    profitMaxim = 0
    for o in ob:
        if Gmax == 0:
            break
        if o["greutate"] <= Gmax:
            profitMaxim += o["profitTotal"]
            Gmax -= o["greutate"]
        else:
            profitMaxim += o["profitKg"] * Gmax
            Gmax = 0
    return profitMaxim


Gmax, ob = citire()
print(f"{greedy(Gmax, sortare(ob)):g}")

De ce este corect

Corectitudinea se arată printr-un schimb de cantități. Se consideră o soluție optimă oarecare. Dacă ea ia x kilograme dintr-un obiect cu profitKg mai mic, deși dintr-un obiect cu profitKg mai mare a rămas neluată o cantitate r, atunci se scot din primul obiect y = min(x, r) kilograme și se iau în locul lor y kilograme din obiectul mai eficient. Greutatea totală rămâne aceeași, deci admisibilă, iar profitul crește cu y înmulțit cu diferența celor două valori profitKg, deci nu scade.

Prin repetarea schimburilor se obține o soluție optimă în care fiecare obiect este luat cât mai mult posibil înaintea obiectelor cu profitKg mai mic, adică exact soluția construită de algoritmul greedy. Prin urmare, alegerea greedy este sigură.

De ce nu este corect pentru rucsacul discret

În varianta discretă, un obiect se ia ori întreg, ori deloc. Nu este permisă fracționarea lui. Criteriul profitKg, adică al eficienței, poate alege un obiect care ocupă spațiul necesar unei combinații mai bune.

Exemplu: Gmax este 50, iar obiectele sunt aceleași:

Greedy alege A și B, cu profitul 160. Soluția optimă discretă alege B și C, cu profitul 220. Așadar, pentru rucsacul discret se folosesc alte metode, precum programarea dinamică, nu greedy în forma de mai sus.

Problema spectacolelor

Enunțul problemei

O casă de cultură are o singură sală. Pentru stagiunea următoare au venit n cereri: fiecare trupă spune la ce oră vrea să înceapă și la ce oră termină.

În sală nu pot avea loc două spectacole în același timp, iar o cerere se acceptă întreagă sau deloc: spectacolul nu se scurtează și nu se mută la altă oră. Deoarece unele cereri se suprapun, nu pot fi acceptate toate.

Se cere numărul maxim de spectacole care pot fi programate.

Formal, se dau n spectacole; spectacolul i are oraInceput și oraSfarsit. Se cere o submulțime de spectacole care nu se suprapun două câte două și care are cât mai multe elemente.

Date de intrare. Pe prima linie, n. Pe fiecare dintre următoarele n linii, denumirea, ora de început și ora de sfârșit ale unui spectacol.

Date de ieșire. Numărul maxim de spectacole care pot fi programate.

Ideea de rezolvare

Condiția se scrie:

oraInceput ≥ oraSfarsit a ultimului acceptat

Criteriul greedy corect este alegerea spectacolului care se termină cel mai devreme dintre spectacolele compatibile. Eliberează sala cât mai repede și lasă cel mai mult timp pentru spectacolele următoare.

Algoritmul

1. Ordonează spectacolele crescător după oraSfarsit.
2. Pune în soluție primul spectacol, cel care se termină cel mai devreme: sol[1] ← sp[1], iar k devine 1.
3. Parcurge restul spectacolelor în această ordine.
4. Acceptă spectacolul i dacă sp[i].oraInceput ≥ sol[k].oraSfarsit.
5. La acceptare, k crește cu 1, iar spectacolul intră în sol.

Schema logică

Cele două scheme au aceeași structură: o sortare, apoi o singură parcurgere cu o decizie în interiorul ei. Diferă criteriul de sortare și prelucrările de pe ramuri.

Exemplu

11
A 1 4
B 3 5
C 0 6
D 5 7
E 3 9
F 5 9
G 6 10
H 8 11
I 8 12
J 2 14
K 12 16

După sortarea după sfârșit, se aleg A, D, H și K. Sunt patru spectacole, iar programul scrie 4.

citește n și cele n spectacole

sortează spectacolele crescător după oraSfarsit

sol[1] ← sp[1]
k ← 1
pentru i ← 2, n:
    dacă sp[i].oraInceput ≥ sol[k].oraSfarsit:
        k ← k + 1
        sol[k] ← sp[i]

scrie k

#include <iostream>
using namespace std;

const int MAX = 101;

struct spectacol {
    char denumire[20];
    int oraInceput, oraSfarsit;
} sp[MAX];

int n, k;
spectacol sol[MAX];

void citire() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> sp[i].denumire
           >> sp[i].oraInceput >> sp[i].oraSfarsit;
}

void sortare() {
    spectacol aux;
    for (int i = 1; i <= n - 1; i++)
        for (int j = i + 1; j <= n; j++)
            if (sp[i].oraSfarsit > sp[j].oraSfarsit) {
                aux = sp[i];
                sp[i] = sp[j];
                sp[j] = aux;
            }
}

void greedy() {
    sol[1] = sp[1];
    k = 1;
    for (int i = 2; i <= n; i++)
        if (sp[i].oraInceput >= sol[k].oraSfarsit)
            sol[++k] = sp[i];
}

void afisare() {
    cout << k;
}

int main() {
    citire();
    sortare();
    greedy();
    afisare();
}

def citire():
    n = int(input())
    sp = []
    for _ in range(n):
        denumire, oraInceput, oraSfarsit = input().split()
        sp.append({
            "denumire": denumire,
            "oraInceput": int(oraInceput),
            "oraSfarsit": int(oraSfarsit)
        })
    return sp


def sortare(sp):
    return sorted(sp, key=lambda s: s["oraSfarsit"])


def greedy(sp):
    sol = [sp[0]]
    for s in sp[1:]:
        if s["oraInceput"] >= sol[-1]["oraSfarsit"]:
            sol.append(s)
    return sol


sp = sortare(citire())
print(len(greedy(sp)))

De ce este corect

Fie G spectacolul compatibil care se termină cel mai devreme și fie O un prim spectacol dintr-o soluție optimă. Deoarece G se termină cel mai devreme, el se termină cel târziu când se termină O.

În soluția optimă, O poate fi înlocuit cu G: orice spectacol care urma după O începe cel mai devreme în momentul în care se termină G, deci rămâne compatibil. Numărul spectacolelor nu scade. După această înlocuire, problema rămasă este aceeași, pentru spectacolele care încep cel mai devreme în momentul în care se termină G. Prin inducție, alegerile greedy produc un număr maxim de spectacole.

Compararea criteriilor greedy

Criteriul corect depinde de problemă:

Nu se alege automat obiectul cu valoarea cea mai mare, cu greutatea cea mai mică sau cu durata cea mai mică. Criteriul trebuie dedus din obiectivul problemei și demonstrat.

Complexitatea metodei

Dacă există n candidați și aceștia trebuie sortați, sortarea are ordinul O(n log n), iar parcurgerea, O(n). Complexitatea totală este O(n log n).

Memoria suplimentară este O(n) dacă se creează o copie sau o structură pentru ordonare. Dacă sortarea se face în aceeași structură, memoria suplimentară poate fi mai mică, în funcție de implementare.

Metoda greedy la examen

În programa de concurs

Metoda este trecută anume în programele de examen, și la Definitivat, și la Titularizare, la capitolul Metode de programare:

metoda greedy: descriere, oportunitatea utilizării metodei, aplicații specifice (de exemplu problema rucsacului în varianta continuă, problema spectacolelor)

Ce s-a dat până acum

În variantele publicate între 2002 și 2026, metoda apare astfel:

Problemele din 2004, 2017, 2018 și 2021 sunt rezolvate, una lângă alta, cu simulator pentru fiecare, la Probleme rezolvate: Metoda greedy.

La Subiectul I, cel de specialitate, metoda greedy nu a fost încă subiect de prezentare. Au fost însă cerute, an de an, alte metode și structuri:

• mergesort;
• bubblesort;
• metoda inserției;
• algoritmul lui Dijkstra;
• parcurgerea în adâncime;
• arborii binari de căutare.

Toate au fost cerute după același plan de idei:

• descriere în limbaj natural și exemplificare a etapelor de aplicare a metodei;
• apreciere a complexității algoritmului corespunzător, din punctul de vedere al duratei de executare;
• un exemplu de aplicare a metodei în rezolvarea unei probleme (enunț, implementare în limbaj de programare a unei soluții, descriere a soluției).

Pentru un asemenea subiect se pregătesc, așadar, trei lucruri: descrierea metodei cu un exemplu lucrat, complexitatea și o problemă rezolvată, cu enunț și program.

Un subiect la care greedy pierde puncte

La Titularizare 2020, Subiectul al II-lea, se cerea numărul maxim de termeni ai unui subșir strict crescător format numai din termeni pari, cu mențiunea „utilizați un algoritm eficient din punctul de vedere al timpului de executare”. Baremul spune, la cei 7 puncte pentru determinarea răspunsului:

pentru algoritm principial corect, dar care conduce la o rezolvare parțială, sau pentru algoritm greedy euristic se acordă numai 3p

Pentru șirul din exemplul subiectului, termenii pari sunt, în ordine:

28 10 42 24 94 30 80 2 4 6 8

Un algoritm greedy care acceptă fiecare termen mai mare decât ultimul acceptat alege 28, 42, 94, deci trei termeni. Răspunsul corect este 4, dat de 10, 24, 30, 80 sau de 2, 4, 6, 8.

Alegerea lui 28 este cea mai bună la primul pas, pentru că este primul termen par. Ea elimină însă toți termenii mai mici care urmează, printre care se află subșirul de lungime 4.

Greșeli frecvente la examen

1. Se aplică greedy fără demonstrarea criteriului de alegere.
2. Se sortează crescător după criteriul care trebuia ordonat descrescător.
3. La spectacole se sortează după oraInceput, nu după oraSfarsit.
4. Se acceptă un spectacol care începe înainte de terminarea celui precedent.
5. La rucsacul continuu se uită calculul lui profitKg și se sortează după profitTotal, adică după profitul întreg, nu după cel pe kilogram.
6. Se aplică soluția rucsacului continuu la rucsacul discret.
7. Se uită fracțiunea din ultimul obiect.
8. Se confundă soluția validă cu soluția optimă.
9. Se schimbă criteriul în timpul algoritmului fără justificare.
10. Se numără obiecte sau spectacole care nu respectă capacitatea ori compatibilitatea.