SISergiu Ilincameditații informatică
Meniu

clasa a XI-a · Metode de programare · lecția 15

Metoda Greedy

60 minintensiv informatică / olimpiadăintensiv

Înainte de lecția asta: X.4 Sortarea vectorilor: bule, selecție, inserție (și sort din STL), X.12 Structuri de date neomogene: struct (înregistrări)

Ce vei ști după lecție

  • Înțelegi ideea Greedy: la fiecare pas alegi varianta care pare cea mai bună acum.
  • Rezolvi problemele clasice: spectacole, rucsac fracționar, plata cu număr minim de monede (când merge).
  • Știi să verifici (sau să combați cu un contraexemplu) corectitudinea unei strategii greedy.

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a XI-aLecția 15 din 21 · mai sunt 6Urmează: XI.16 · Programare dinamică: idee, recurențe, probleme clasiceVezi toate lecțiile
Cuprins

Fișiere PDF și de lucru

1. Ideea: alegerea „lacomă”

Ai de dat rest 276 de lei și vrei cât mai puține bancnote. Natural: dai întâi cea mai mare bancnotă care încape (200), apoi 50, 10, 10, 5, 1. La fiecare pas ai făcut alegerea cea mai bună în acel moment și nu te-ai mai răzgândit. Asta este metoda Greedy (lacomă).

Schema generală:

  1. ordonezi candidații după un criteriu bine ales (aici e toată arta);
  2. parcurgi candidații în ordine; pe fiecare îl iei dacă nu strică ce ai deja;
  3. nu te întorci niciodată asupra unei alegeri.

Atenție — greșeli frecvente

Greedy este rapid (de obicei O(n log n), cât costă sortarea), dar nu merge întotdeauna. Un criteriu care „pare” bun poate da răspunsuri greșite. Regula de aur: caută un contraexemplu înainte să scrii codul.

2. Problema spectacolelor

Sunt n spectacole, fiecare cu ora de început și ora de sfârșit. Ce număr maxim de spectacole poate vedea o persoană fără suprapuneri?

Trei criterii posibile: (a) după ora de început, (b) după durată, (c) după ora de sfârșit. Doar al treilea este corect.

Criteriul durata, greșit

De ce după sfârșit? Spectacolul care se termină cel mai devreme îți lasă cel mai mult timp liber pentru restul. Orice soluție optimă poate fi „schimbată” să înceapă cu el fără să piardă niciun spectacol (argument de schimb: dacă soluția optimă începe cu alt spectacol, care se termină mai târziu, îl înlocuiești cu cel mai devreme terminat; nu se suprapune cu nimic din restul).

Spectacole

Trace pe cele 8 spectacole, sortate după sfârșit:

Spectacol (st–sf) st ≥ ultimSf? Ce fac ultimSf
1–4 1 ≥ 0 da îl aleg 4
3–5 3 ≥ 4 nu sar 4
0–6 0 ≥ 4 nu sar 4
5–7 5 ≥ 4 da îl aleg 7
3–8 3 ≥ 7 nu sar 7
5–9 5 ≥ 7 nu sar 7
6–10 6 ≥ 7 nu sar 7
8–11 8 ≥ 7 da îl aleg 11
#include <iostream>
#include <algorithm>
using namespace std;

struct spectacol { int st, sf; } v[1001];
int n;

bool cmp(spectacol a, spectacol b)
{
    return a.sf < b.sf;                       // crescător după ora de sfârșit
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i].st >> v[i].sf;
    sort(v + 1, v + n + 1, cmp);

    int ultim = 0, nr = 0;
    spectacol ales[1001];
    for (int i = 1; i <= n; i++)
        if (v[i].st >= ultim)                 // nu se suprapune cu ultimul ales
        {
            ales[++nr] = v[i];
            ultim = v[i].sf;
        }
    cout << nr << '\n';
    for (int i = 1; i <= nr; i++) cout << ales[i].st << ' ' << ales[i].sf << '\n';
    return 0;
}

De ce așa?

De ce >= și nu >? Un spectacol care începe exact când se termină celălalt nu se suprapune (de la 4 la 4 nu e timp comun). Verifică în enunț dacă „se suprapun” include și capetele. De ce sortare cu o funcție cmp? sort știe să ordoneze numere, nu structuri; îi spui tu cum compară două spectacole.

Intrare / ieșire

Intrare Ieșire
8 · 1 4 · 3 5 · 0 6 · 5 7 · 3 8 · 5 9 · 6 10 · 8 11 3 · 1 4 · 5 7 · 8 11

3. Rucsacul fracționar

Ai un rucsac de capacitate C și n obiecte, fiecare cu greutate G și valoare V. Poți lua fracțiuni din obiecte (ca la făină sau nisip). Care este valoarea maximă?

Criteriul: raportul V/G (lei pe kilogram), în ordine descrescătoare. Umpli rucsacul cu „cea mai scumpă făină” mai întâi.

Rucsac

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;

struct obiect { double g, v; } o[101];
int n;

bool cmp(obiect a, obiect b)
{
    return a.v / a.g > b.v / b.g;             // raport descrescător
}

int main()
{
    double C;
    cin >> n >> C;
    for (int i = 1; i <= n; i++) cin >> o[i].g >> o[i].v;
    sort(o + 1, o + n + 1, cmp);

    double total = 0;
    for (int i = 1; i <= n && C > 0; i++)
    {
        if (o[i].g <= C)                      // încape întreg
        {
            total += o[i].v;
            C -= o[i].g;
        }
        else                                  // luăm doar o fracțiune
        {
            total += o[i].v * C / o[i].g;
            C = 0;
        }
    }
    cout << fixed << setprecision(2) << total;
    return 0;
}

De ce așa?

De ce raportul V/G și nu doar V? Un obiect cu valoare mare dar foarte greu „consumă” capacitatea. Contează câtă valoare obții pe unitatea de capacitate. De ce nu merge pentru obiecte întregi? Cu aceleași date și obiecte nefracționabile, greedy ia obiectele 1 și 2 (30 kg, 160 lei) și nu mai încape al treilea; dar obiectele 2 și 3 încap (50 kg, 220 lei). Fracțiunea este ceea ce face criteriul optim; fără ea trebuie programare dinamică (lecția XI.16).

4. Rest cu număr minim de bancnote

Cu bancnotele românești 500, 200, 100, 50, 10, 5, 1: dai mereu cea mai mare bancnotă care încape. Pentru 276: 200 + 50 + 10 + 10 + 5 + 1.

#include <iostream>
using namespace std;

int main()
{
    int b[] = {500, 200, 100, 50, 10, 5, 1};
    int S;
    cin >> S;
    for (int i = 0; i < 7; i++)
        while (S >= b[i])
        {
            cout << b[i] << ' ';
            S -= b[i];
        }
    return 0;
}

Greedy greșește

Atenție — greșeli frecvente

Pentru alt sistem de monede greedy poate greși: cu monede {1, 3, 4} și suma 6, greedy dă 4 + 1 + 1 (3 monede), iar optimul este 3 + 3 (2 monede). Greedy funcționează pe bancnotele reale pentru că fiecare valoare este multiplu convenabil al celor mai mici; pentru un set oarecare de monede se folosește programare dinamică.

5. Clienți la casă: cei rapizi primii

n clienți, fiecare cu durata de servire tᵢ, la o singură casă. În ce ordine îi servim ca suma timpilor de așteptare (până când începe să fie servit fiecare) să fie minimă?

Clienți

De ce cei rapizi primii? Durata primului client se adaugă la așteptarea tuturor celorlalți, durata celui de-al doilea la așteptarea tuturor celor de după el, și tot așa. Un client cu durată mare pus primul ar „taxa” pe toți ceilalți.

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n, t[101];
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> t[i];
    sort(t + 1, t + n + 1);                   // cei mai rapizi primii

    long long asteptare = 0, curent = 0;
    for (int i = 1; i <= n; i++)
    {
        asteptare += curent;                   // clientul i așteaptă cât au durat cei dinaintea lui
        curent += t[i];
    }
    cout << asteptare;
    return 0;
}

De ce așa?

De ce long long? Pentru 100 000 de clienți cu timpi mari, suma depășește 2·10⁹. Fă un obicei: dacă adunăm multe valori, long long.

Trace pentru t = 5 2 8 1 (după sortare 1 2 5 8):

i t[i] asteptare += curent curent
1 1 0 1
2 2 1 3
3 5 4 8
4 8 12 16

6. Cum alegi criteriul și cum verifici

Problemă Criteriu corect Criteriu care pare bun, dar greșește
spectacole ora de sfârșit durata; ora de început
rucsac fracționar raport V/G doar V; doar G
clienți la casă durata crescător ordinea sosirii
rest cu bancnote reale cea mai mare care încape (merge)
rest cu monede {1, 3, 4} — cea mai mare care încape (greșește)

Ghid în trei pași:

  1. propune un criteriu;
  2. încearcă să-l spargi cu cazuri mici (n = 3 sau 4), cu cazuri „la limită” (egalități);
  3. dacă nu găsești contraexemple, încearcă un argument de schimb: „dacă soluția optimă ar face altfel, o pot transforma în una cel puțin la fel de bună care face ca criteriul meu”.

7. Greșeli frecvente

Greșeala Efect Corect
spectacole sortate după început rezultat prea mic după sfârșit
cmp cu <= sort poate bloca sau da eroare < strict
rucsac cu int și diviziune V / G întreg, zero double
ultim = 0 și spectacole care încep la 0, cu > pierzi primul >=
criteriu neverificat greșit pe unele teste contraexemple

8. Exersează pe hârtie

1. Găsește un contraexemplu pentru „la spectacole, alege mereu spectacolul care începe cel mai devreme”.

2. Spectacole: (1,3), (2,5), (4,6), (6,8), (5,9), (8,10). Câte alege greedy (după sfârșit)?

3. Rucsac fracționar, C = 10, obiecte (G, V): (4, 8), (5, 6), (6, 12). Care este valoarea maximă?

4. Rest de 289 lei cu bancnotele 500, 200, 100, 50, 10, 5, 1. Câte bancnote minime?

5. Cu monede {1, 5, 6, 9} și suma 11, ce dă greedy? Care este optimul?

6. Clienți cu duratele 3, 1, 4, 2: care este suma timpilor de așteptare în ordinea sosirii? Dar în ordinea optimă?

7. Se dau n numere întregi și un număr k. Alege exact k numere cu suma maximă. Ce strategie folosești?

8. (BAC) Se dau n activități cu termen limită și profit, fiecare durând o unitate de timp. Dacă poți face o activitate pe unitate de timp, în ce ordine ai alege activitățile? (Idee: cele cu profit maxim primele.)

9. Se dă un număr cu cifre. Elimină k cifre ca numărul rămas să fie maxim. Pentru 1924 și k = 2 ce obții?

10. Spune dacă greedy-ul „ia mereu cea mai mare monedă care încape” este corect pentru monedele {1, 2, 5, 10, 20, 50}. Încearcă să găsești un contraexemplu.

9. Mai departe (pentru cine vrea mai mult)

Elimină k cifre pentru numărul maxim. Parcurgi cifrele; cât timp ultima cifră păstrată este mai mică decât cea curentă și mai ai de eliminat, o scoți.

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    char s[105], r[105];
    int k, lung = 0;
    cin >> s >> k;
    int n = strlen(s);
    for (int i = 0; i < n; i++)
    {
        while (k > 0 && lung > 0 && r[lung - 1] < s[i])
        {
            lung--;                              // scoatem o cifră mai mică din urmă
            k--;
        }
        r[lung++] = s[i];
    }
    lung -= k;                                    // dacă au rămas de eliminat, tăiem de la coadă
    r[lung] = 0;
    cout << r;
    return 0;
}

Argumentul de schimb, pe scurt. Pentru a arăta că un greedy e corect, presupui o soluție optimă care nu respectă alegerea greedy și arăți că o poți modifica, fără să o înrăutățești, ca să o respecte. Se repetă pas cu pas.

Alte probleme clasice. Acoperire de intervale cu număr minim de segmente; cel mai scurt drum cu costuri pozitive (Dijkstra, lecția XI.19); arbore parțial de cost minim (Prim, Kruskal); coduri Huffman (compresie).

Greedy sau programare dinamică? Dacă ai un contraexemplu pentru alegerea locală, sau dacă alegerea de acum depinde de ce faci mai târziu, ai nevoie de programare dinamică (XI.16).

Rezumat

  • Greedy: sortezi după un criteriu, iei ce încape, nu te mai întorci.
  • Spectacole: după ora de sfârșit. Rucsac fracționar: după V/G. Clienți: durata crescător.
  • Nu merge întotdeauna (monede {1, 3, 4}, rucsac discret): caută contraexemple.
  • Sortare cu cmp strict (<); sume mari în long long.

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 120 min

Greedy și programare dinamică

  • Decizi dacă un criteriu greedy este corect sau îl dărâmi cu un contraexemplu mic.
  • Completezi de mână tabele de programare dinamică (scări, drumuri, SCLM, rucsac, monede).
  • Scrii starea, recurența, baza și răspunsul pentru o problemă nouă, apoi codul.

Fișa acoperă și: XI.16

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • spectacole#353

    ușoară
  • masini#91

    ușoară
  • kmax#1877

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • proiecte#92

    ușoară
  • bomboane#341

    ușoară
  • prodmax1#2271

    ușoară
  • alimentarea-masinii#4220

    ușoară
  • rucsac#1340

    Varianta fracționară: sortare după valoare/greutate.

    medie
  • pachete#400

    medie

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. Spectacole (0,10), (1,2), (3,4): cel mai devreme începe (0,10), care acoperă tot; greedy ia 1 spectacol, optimul este 2 ((1,2) și (3,4)).

2. Sortate după sfârșit: (1,3), (2,5), (4,6), (6,8), (5,9), (8,10). Alege (1,3), apoi (4,6) (4 ≥ 3), apoi (6,8) (6 ≥ 6), apoi (8,10): 4 spectacole.

3. Rapoarte: 2, 1,2, 2. Obiectele 1 (4 kg, 8 lei) și 3 (6 kg, 12 lei) au raportul 2; le luăm întregi: 10 kg, 20 lei. Valoarea maximă: 20.

4. 289 = 200 + 50 + 10 + 10 + 10 + 5 + 1 + 1 + 1 + 1: 10 bancnote. Verificare: 200 + 50 = 250; + 30 (3 × 10) = 280; + 5 = 285; + 4 × 1 = 289.

5. Greedy: 9 + 1 + 1 (3 monede); optim: 5 + 6 (2 monede).

6. În ordinea sosirii (3, 1, 4, 2): așteptări 0 + 3 + 4 + 8 = 15. Ordinea optimă (1, 2, 3, 4): 0 + 1 + 3 + 6 = 10.

7. Sortezi descrescător și aduni primele k (dacă toate pozitive); cu numere negative tot primele k, fiind cele mai mari.

8. Sortezi activitățile descrescător după profit; fiecare se pune în ultima unitate de timp liberă dinaintea termenului (dacă există); dacă nu există loc, se sare.

9. Rezultatul este 94 (programul din „Mai departe”).

10. Da, pentru {1, 2, 5, 10, 20, 50} greedy este corect (fiecare monedă este multiplu al unei monede mai mici sau are structură care se potrivește): nu există contraexemplu. Greedy nu este corect, de exemplu, pentru {1, 3, 4}.