Metoda greedy

Metoda greedy este o metodă de programare care construiește soluția pas cu pas. La fiecare pas se alege, dintre variantele disponibile, opțiunea care pare cea mai bună în acel moment, fără să se revină asupra alegerii.

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
    dacă adăugarea lui păstrează fezabilitatea:
        adaugă candidatul în soluție
returnează soluția

O alegere este local optimă dacă este cea mai bună dintre variantele disponibile la pasul curent. Soluția finală este global optimă dacă nu există o altă soluție validă cu un rezultat mai bun.

Când este oportună metoda greedy

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

1. proprietatea alegerii greedy: există o soluție optimă care începe cu alegerea locală făcută de algoritm;
2. proprietatea substructurii optime: după alegerea făcută, restul problemei este de același tip, iar o soluție optimă pentru rest completează o soluție optimă pentru problema inițială.

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 cod, se răspund 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 să revenim asupra alegerii?
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 — făină, zahăr, orez — fiecare cu greutatea ei și cu profitul pe care îl aduce.

Fiind vrac, 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. De aici vine denumirea varianta continuă, spre deosebire de varianta discretă, în care un obiect se ia întreg sau deloc.

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

Formal: avem 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. Calculează profitKg pentru fiecare obiect.
2. Ordonează obiectele descrescător după profitKg.
3. Parcurge obiectele în această ordine, cât timp mai există loc.
4. Dacă obiectul încape integral, ia-l întreg și scade-i greutatea din Gmax.
5. Altfel, ia doar fracțiunea care mai încape, adaugă profitKg · Gmax la profit și fă Gmax zero — rucsacul s-a umplut.

Schema logică

Din desen se vede că nicio săgeată nu urcă înapoi la 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 bucla se oprește. 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

Fie obiectul cu cel mai mare profitKg care nu a fost încă ales. Dacă într-o soluție optimă apare înaintea lui un obiect cu profitKg mai mic, putem înlocui o parte din acel obiect cu aceeași greutate din obiectul mai eficient. Greutatea totală rămâne admisibilă, iar profitul nu scade.

Repetând înlocuirea, obținem o soluție optimă care ia obiectele în ordinea descrescătoare a lui profitKg. 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 densității 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: avem n spectacole, spectacolul i având 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

Două spectacole sunt compatibile dacă al doilea începe după sau exact când se încheie primul:

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ă, îl putem înlocui pe O cu G: orice spectacol care urma după O începe și după G, deci rămâne compatibil. Numărul spectacolelor nu scade. După această înlocuire, problema rămasă este aceeași, dar începe după sfârșitul lui 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 costă O(n log n), iar parcurgerea costă 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 2018 și 2026 — nouă la Definitivat și opt la Titularizare — metoda apare de două ori, de fiecare dată altfel:

La Subiectul I, cel de specialitate, metoda greedy nu a fost încă subiect de prezentare. Au fost însă, an de an, alte metode și structuri — mergesort, bubblesort, metoda inserției, algoritmul lui Dijkstra, parcurgerea în adâncime, arbori binari de căutare — 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.