Un festival are mai multe spectacole, fiecare cu ora de început și de final. Programul alege cât mai multe spectacole care nu se suprapun, ca să le vezi pe toate de la cap la coadă.
spectacole.cpp, în consolă
6
1 4
3 5
0 6
5 7
8 9
5 9
3
1 4
5 7
8 9
Primul număr e n, apoi câte un spectacol pe rând. Răspunsul: 3 spectacole, cu orele lor. Soluția încearcă o singură ordine, nu toate combinațiile, și totuși dă optimul.
să recunoști o problemă care se rezolvă greedy
să alegi criteriul după care sortezi
să rezolvi problema spectacolelor
să găsești un contraexemplu când greedy greșește
Pasul 2 din 5
Rulează-l linie cu linie
Cel mai simplu greedy: ai de dat 68 de lei și vrei să folosești un număr minim de bancnote. Ai la dispoziție bancnote de 50, 10, 5 și 1. La fiecare pas iei cât mai multe din bancnota cea mai valoroasă care încape.
bancnote.cpp
#include<iostream>usingnamespace std;intmain() {int b[5] = {0, 50, 10, 5, 1};int s = 68, nr = 0;for (int k = 1; k <= 4; k++) { nr += s / b[k]; s = s % b[k]; } cout << nr;return0;}
Variabile
Ce apare pe ecran
Linia 5. Valorile bancnotelor, în ordine descrescătoare, pe pozițiile 1–4.
Linia 6.s e suma rămasă de plătit, nr numără bancnotele.
Linia 7. Prima bancnotă: 50.
Linia 8. 68 / 50 = 1: încape o singură bancnotă de 50.
Linia 9. Rămân 68 % 50 = 18 lei.
Linia 7. Următoarea bancnotă: 10.
Linia 8. 18 / 10 = 1, încă o bancnotă. nr devine 2.
Linia 9. Rămân 8 lei.
Linia 7. Următoarea: 5.
Linia 8. 8 / 5 = 1. nr devine 3.
Linia 9. Rămân 3 lei.
Linia 7. Ultima: 1.
Linia 8. 3 / 1 = 3 bancnote de 1 leu. nr devine 6.
Linia 9. Nu mai rămâne nimic.
Linia 7.k ar fi 5, iar 5 <= 4 e fals. Bucla se termină, iar k, declarat în for, dispare.
Linia 11. Se afișează 6: 50 + 10 + 5 + 1 + 1 + 1.
Linia 12.main se încheie.
Gata. Programul n-a încercat nicio altă combinație. A ales la fiecare pas ce părea mai bun și nu s-a mai întors.
Prezice ieșirea
Schimbi suma în s = 99. Ce afișează programul?
Răspuns: „10”.
99 = 50 + 4 · 10 + 5 + 4 · 1. Asta înseamnă 1 + 4 + 1 + 4 = 10 bancnote. Cu valorile 50, 10, 5 și 1, greedy dă chiar minimul.
Pasul 3 din 5
Cum gândești greedy
Greedy înseamnă „lacom”: la fiecare pas iei alegerea care arată cel mai bine acum și nu revii asupra ei. Fragmentele stau în main.
1
Sortezi, apoi iei pe rând
sumak.cpp
int v[6] = {0, 4, -2, 7, 1, 9};int n = 5, cate = 2;for (int k = 1; k < n; k++)for (int p = k + 1; p <= n; p++)if (v[k] < v[p]) {int aux = v[k]; v[k] = v[p]; v[p] = aux; }int s = 0;for (int k = 1; k <= cate; k++) s += v[k];cout << s;
Ce apare pe ecran
16
Suma maximă din k = 2 elemente: le ordonezi descrescător și îi iei pe primii k, 9 și 7. Aproape orice greedy are forma asta: o sortare după un criteriu, apoi o parcurgere.
2
Ordinea la ghișeu
ghiseu.cpp
int t[4] = {0, 5, 1, 2};int n = 3;for (int k = 1; k < n; k++)for (int p = k + 1; p <= n; p++)if (t[k] > t[p]) {int aux = t[k]; t[k] = t[p]; t[p] = aux; }int astept = 0, total = 0;for (int k = 1; k <= n; k++) { total += astept; astept += t[k];}cout << total;
Ce apare pe ecran
4
Trei clienți au nevoie de 5, 1 și 2 minute. Ca timpul total de așteptare să fie minim, îi servești întâi pe cei rapizi. În ordinea inițială, totalul ar fi 11.
3
Spectacole: după ora de final
struct Sp
struct Sp {int s, f;};
spectacole.cpp
Sp v[5] = {{}, {1, 4}, {3, 5}, {5, 7}, {8, 9}};int n = 4, nr = 1, ultim = 1;for (int k = 2; k <= n; k++)if (v[k].s >= v[ultim].f) { nr++; ultim = k; }cout << nr;
Ce apare pe ecran
3
Spectacolele sunt deja sortate după final. Îl iei pe primul, apoi pe fiecare care începe după ce s-a terminat ultimul ales. Cine se termină devreme îți lasă cel mai mult timp pentru restul.
4
Când greedy greșește
monede.cpp
int m[4] = {0, 4, 3, 1};int s = 6, nr = 0;for (int i = 1; i <= 3; i++) { nr += s / m[i]; s %= m[i];}cout << nr;
Ce apare pe ecran
3
Cu monede de 4, 3 și 1, suma 6 iese greedy 4 + 1 + 1, adică 3 monede. Optimul e 3 + 3, adică 2. Greedy merge la bancnotele românești, dar nu pentru orice set de valori.
La bac, înainte să scrii un greedy, caută un contraexemplu mic. Dacă îl găsești, ai nevoie de altă metodă, de exemplu programarea dinamică.
Capcană: sortezi după ora de început
Pare firesc să alegi întâi spectacolul care începe primul. Dar dacă acela durează toată ziua, îți blochează tot programul:
start.cpp
Sp v[5] = {{}, {0, 10}, {1, 3}, {4, 6}, {7, 9}};int n = 4, nr = 1, ultim = 1;for (int k = 2; k <= n; k++)if (v[k].s >= v[ultim].f) { nr++; ultim = k; }cout << nr;
Ce apare pe ecran
1
Spectacolul 0–10 a fost ales primul și a exclus celelalte trei. Repară sortând după ora de final: răspunsul devine 3.
Capcană: bancnotele în ordine crescătoare
Același algoritm de plată, dar cu bancnota de 1 leu pe primul loc. Toată suma se plătește în monede de 1:
nesortat.cpp
int b[5] = {0, 1, 5, 10, 50};int s = 68, nr = 0;for (int k = 1; k <= 4; k++) { nr += s / b[k]; s %= b[k];}cout << nr;
Ce apare pe ecran
68
Repară ordonând valorile descrescător. Criteriul de sortare e jumătate din orice soluție greedy.
Pasul 4 din 5
Verifică-te
Cinci grile în stilul bacului. După fiecare răspuns vezi de ce e așa.
1 din 5 · Prezice ieșirea
Ce afișează programul?
plata.cpp
#include<iostream>usingnamespace std;intmain() {int b[5] = {0, 50, 10, 5, 1};int s = 37, nr = 0;for (int k = 1; k <= 4; k++) { nr += s / b[k]; s %= b[k]; } cout << nr;return0;}
Răspuns: „6”.
37 = 3 · 10 + 5 + 2 · 1. Nicio bancnotă de 50, trei de 10, una de 5 și două de 1: 6 bancnote.
2 din 5 · Alege varianta
La problema spectacolelor, după ce criteriu sortezi?
Răspuns: ora de final.
Spectacolul care se termină primul lasă cel mai mult timp liber. Durata pare bună, dar un spectacol scurt poate tăia două spectacole lungi care nu se suprapun între ele.
3 din 5 · Alege varianta
Monedele sunt de 1, 3 și 4. Câte monede folosește greedy pentru suma 6 și câte ar fi optim?
Răspuns: greedy 3, optim 2.
Greedy ia 4, apoi 1 și 1. Optimul e 3 + 3. E contraexemplul din cardul 4.
4 din 5 · Prezice ieșirea
Ce afișează programul?
ghiseu.cpp
#include<iostream>usingnamespace std;intmain() {int t[4] = {0, 4, 1, 3};int n = 3, i, j;int astept = 0, total = 0;for (i = 1; i < n; i++)for (j = i + 1; j <= n; j++)if (t[i] > t[j]) {int aux = t[i]; t[i] = t[j]; t[j] = aux; }for (i = 1; i <= n; i++) { total += astept; astept += t[i]; } cout << total;return0;}
Răspuns: „5”.
După sortare, timpii sunt 1, 3, 4. Primul client așteaptă 0, al doilea 1, al treilea 1 + 3 = 4. Totalul e 0 + 1 + 4 = 5.
5 din 5 · Alege varianta
Care afirmație despre metoda greedy e adevărată?
Răspuns: alegeri locale, fără întoarcere.
Încercarea tuturor combinațiilor e backtracking. Greedy e rapid tocmai pentru că nu se întoarce, dar asta îl face să greșească la probleme ca monedele 1, 3, 4.
Pasul 5 din 5
Ce ai învățat
Greedy face la fiecare pas alegerea care arată cel mai bine acum și nu revine asupra ei.
Forma obișnuită: sortezi după un criteriu, apoi parcurgi și alegi.
La spectacole, criteriul corect e ora de final, crescător.
Greedy nu dă mereu optimul. Un contraexemplu mic îți arată când trebuie altă metodă.
Programul complet
Citire, sortare după final cu interschimbare de structuri, apoi alegerea. A doua parcurgere refolosește aceeași regulă ca să afișeze spectacolele alese.
spectacole.cpp
#include<iostream>usingnamespace std;struct Sp {int s, f;};intmain() { Sp v[101];int n, i, j; cin >> n;for (i = 1; i <= n; i++) cin >> v[i].s >> v[i].f;for (i = 1; i < n; i++)for (j = i + 1; j <= n; j++)if (v[i].f > v[j].f) { Sp aux = v[i]; v[i] = v[j]; v[j] = aux; }int nr = 1, ultim = 1;for (i = 2; i <= n; i++)if (v[i].s >= v[ultim].f) { nr++; ultim = i; } cout << nr << '\n'; ultim = 1; cout << v[1].s << ' ' << v[1].f;for (i = 2; i <= n; i++)if (v[i].s >= v[ultim].f) { ultim = i; cout << '\n' << v[i].s; cout << ' ' << v[i].f; }return0;}