Ce vei învăța astăzi?
După această lecție vei înțelege că Divide et impera și Greedy nu se exclud: adesea D&I pregătește datele (sortează, prelucrează), iar Greedy ia deciziile, sau invers, Greedy construiește soluția, iar D&I o verifică.
De ce combinăm cele două metode?
Definiție: O problemă combinată folosește ambele metode, fiecare pentru partea ei: Divide et impera organizează datele (sortare prin interclasare, căutare binară, prelucrare pe intervale), iar metoda Greedy alege optimul local (cea mai bună alegere la pasul curent, fără reconsiderare) pe datele deja pregătite. Ordinea poate fi inversată: Greedy construiește o soluție, iar o funcție recursivă de tip D&I o verifică.
Sortăm, căutăm, prelucrăm intervalele în O(n log n) sau O(log n)
Alegem optimul local pas cu pas, pe datele deja ordonate
O funcție recursivă confirmă corectitudinea soluției construite
Analogie: organizarea unui festival
Directorul unui festival trebuie să aleagă cât mai multe concerte compatibile, dintr-o listă lungă de propuneri. Mai întâi, o echipă sortează propunerile după ora de terminare (etapă de organizare, ușor de făcut cu interclasare, de tip D&I). Apoi, directorul alege concertele pas cu pas, cu regula greedy „cel mai devreme sfârșit". La final, un verificator parcurge lista aleasă și confirmă că niciun concert nu se suprapune cu următorul. Cele două metode au lucrat împreună, fiecare pentru ce știe mai bine.
Rucsacul fracționar: interclasare + umplere greedy
Prima problemă combinată: obiectele se sortează prin interclasare (Divide et impera) după eficiență, apoi rucsacul se umple greedy. Fiecare metodă rezolvă o etapă clară, iar programul este complet, stil Bacalaureat.
#include <iostream>
using namespace std;
int valoare[100001], greutate[100001];
int vTemp[100001], gTemp[100001];
bool maiEficient(int i, int j) {
return valoare[i] * 1LL * greutate[j] > valoare[j] * 1LL * greutate[i];
}
void interclaseaza(int st, int mij, int dr) {
int i = st, j = mij + 1, k = st;
while (i <= mij && j <= dr) {
if (maiEficient(i, j)) {
vTemp[k] = valoare[i];
gTemp[k] = greutate[i];
k++; i++;
} else {
vTemp[k] = valoare[j];
gTemp[k] = greutate[j];
k++; j++;
}
}
while (i <= mij) {
vTemp[k] = valoare[i];
gTemp[k] = greutate[i];
k++; i++;
}
while (j <= dr) {
vTemp[k] = valoare[j];
gTemp[k] = greutate[j];
k++; j++;
}
for (int p = st; p <= dr; p++) {
valoare[p] = vTemp[p];
greutate[p] = gTemp[p];
}
}
void sorteaza(int st, int dr) {
if (st < dr) {
int mij = (st + dr) / 2;
sorteaza(st, mij);
sorteaza(mij + 1, dr);
interclaseaza(st, mij, dr);
}
}
int main() {
int n, g;
cin >> n >> g;
for (int i = 1; i <= n; i++) {
cin >> valoare[i] >> greutate[i];
}
sorteaza(1, n);
double castig = 0;
for (int i = 1; i <= n && g > 0; i++) {
if (greutate[i] <= g) {
castig += valoare[i];
g -= greutate[i];
} else {
castig += valoare[i] * 1.0 * g / greutate[i];
g = 0;
}
}
cout << castig << endl;
return 0;
}
Ce învățăm: primele linii (până la sorteaza(1, n)) sunt 100% Divide et impera, iar bucla de umplere este 100% Greedy. Programul arată cum se îmbină cele două metode într-un singur flux logic.
Spectacolele: selecție greedy + verificare prin D&I
A doua problemă combinată: Greedy construiește lista de spectacole compatibile (sortare după sfârșit + alegere), apoi o funcție recursivă de tip Divide et impera verifică, pe intervale, că nicio pereche de spectacole consecutive alese nu se suprapune. Dacă toate granițele sunt compatibile, soluția este corectă prin construcție și prin verificare.
#include <iostream>
using namespace std;
int inceput[101], sfarsit[101];
int alese[101];
int nrAlese = 0;
void sorteaza(int n) {
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (sfarsit[i] > sfarsit[j]) {
int aux = sfarsit[i];
sfarsit[i] = sfarsit[j];
sfarsit[j] = aux;
aux = inceput[i];
inceput[i] = inceput[j];
inceput[j] = aux;
}
}
}
}
void selecteazaGreedy(int n) {
alese[1] = 1;
nrAlese = 1;
int ultimul = sfarsit[1];
for (int i = 2; i <= n; i++) {
if (inceput[i] >= ultimul) {
nrAlese++;
alese[nrAlese] = i;
ultimul = sfarsit[i];
}
}
}
bool compatibil(int a, int b) {
return sfarsit[alese[a]] <= inceput[alese[b]];
}
bool verifica(int st, int dr) {
if (st >= dr) {
return true;
}
int mij = (st + dr) / 2;
if (!verifica(st, mij)) {
return false;
}
if (!verifica(mij + 1, dr)) {
return false;
}
return compatibil(mij, mij + 1);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> inceput[i] >> sfarsit[i];
}
sorteaza(n);
selecteazaGreedy(n);
if (verifica(1, nrAlese)) {
cout << "Soluția greedy este corectă: " << nrAlese << " spectacole" << endl;
}
return 0;
}
Ce învățăm: funcția verifica(st, dr) descompune lista aleasă în jumătăți, verifică recursiv fiecare jumătate și apoi granița dintre ele. Dacă toate granițele sunt compatibile, atunci toate perechile sunt compatibile: este exact principiul descompunere-rezolvare-combinare aplicat verificării.
inceput[i+1] >= sfarsit[i]); un singur if scris greșit lasă suprapuneri neobservate.Aprofundare
Cum recunoști o problemă combinată: caută două cerințe distincte în enunț: una de organizare a datelor („sortează", „caută", „interclasează") și una de alegere („număr minim", „valoare maximă", „cât mai multe"). Dacă le găsești pe amândouă, problema se rezolvă probabil combinând D&I cu Greedy. Uneori prima metodă este ascunsă: de exemplu, „sortează eficient" înseamnă merge sort, nu sortare prin selecție.
De ce nu se verifică toate perechile? La verificarea spectacolelor, a verifica toate perechile ar însemna O(n) comparații. Verificarea D&I compară doar perechile de la granițele jumătăților, în O(n log n) — dar este corectă doar pentru perechi consecutive dintr-o listă ordonată după sfârșit: dacă oricare două spectacole consecutive nu se suprapun, atunci nicio pereche oarecare nu se suprapune. Această proprietate se numește „compatibilitate tranzitivă pe lista ordonată" și trebuie înțeleasă înainte de a folosi varianta rapidă.
Alte combinații frecvente: căutare binară pentru a găsi primul spectacol compatibil cu unul dat, în loc de parcurgere liniară; interclasarea a două liste de activități deja sortate, pentru a selecta apoi greedy din lista rezultată; numărarea inversiunilor pentru a măsura cât de departe este o listă de ordinea dorită înainte de alegerea greedy.
Ordinea contează: în majoritatea problemelor, D&I precede Greedy (pregătește datele), dar există și situații inverse, în care Greedy produce soluția, iar D&I o validează sau o optimizează. Citește enunțul și decide rolul fiecărei metode înainte de a scrie codul.
Exemplu din viața reală: o firmă de logistică primește comenzi cu greutăți și valori și are o singură mașină de transport. Mai întâi sortează comenzile după valoare pe kilogram (organizare, D&I), apoi încarcă mașina greedy. Înainte de plecare, un program de control verifică recursiv că încărcătura respectă limitele pe fiecare segment al traseului. Exact combinația de metode studiată astăzi.
Exercițiu de completare
Completează enunțul despre problemele combinate:
Într-o problemă combinată, Divide et impera ______ datele (de exemplu, sortarea prin ______), iar Greedy ______ optimul local. Uneori, Greedy construiește soluția, iar o funcție recursivă de tip D&I o ______.
Bancă de cuvinte:
Exercițiu de completare: verificarea D&I
Completează descrierea funcției verifica:
Funcția verifica(st, dr) are cazul de bază st >= ______. La combinare, verifică mai întâi jumătățile, apoi granița compatibil(______, mij + 1). Verificarea este corectă doar pentru lista ______ după sfârșit, pentru că atunci granițele acoperă toate perechile ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - probleme combinate:
1. În rucsacul fracționar combinat, rolul interclasării este:
2. Cazul de bază al funcției verifica(st, dr) este:
3. Verificarea D&I a spectacolelor compară:
PbInfo - Rucsac fracționar combinat
Enunț:
Cerință: Se dau n obiecte cu valoare și greutate și capacitatea g. Obiectele se pot lua și fracționar. Să se afișeze valoarea maximă, cu două zecimale, folosind obligatoriu sortarea prin interclasare pentru ordonarea după eficiență și apoi umplerea greedy.
Date de intrare:
Programul citește n și g, apoi n perechi valoare greutate.
Date de ieșire:
Programul va afișa valoarea maximă cu două zecimale.
Restricții și precizări:
1 ≤ n ≤ 100000; 1 ≤ g ≤ 1000000000; valorile și greutățile sunt numere naturale mai mici decât 1000000000.
Exemplu:
Intrare:
3 10 60 10 100 20 120 30
Ieșire:
240.00
Cum gândim soluția:
- Sortăm obiectele prin interclasare, după eficiență descrescătoare (D&I)
- Umplem rucsacul greedy: întreg dacă încape, fracțiune altfel
- Afișăm câștigul cu două zecimale
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
#include <iomanip>
using namespace std;
int valoare[100001], greutate[100001];
int vTemp[100001], gTemp[100001];
bool maiEficient(int i, int j) {
return valoare[i] * 1LL * greutate[j] > valoare[j] * 1LL * greutate[i];
}
void interclaseaza(int st, int mij, int dr) {
int i = st, j = mij + 1, k = st;
while (i <= mij && j <= dr) {
if (maiEficient(i, j)) {
vTemp[k] = valoare[i];
gTemp[k] = greutate[i];
k++; i++;
} else {
vTemp[k] = valoare[j];
gTemp[k] = greutate[j];
k++; j++;
}
}
while (i <= mij) {
vTemp[k] = valoare[i];
gTemp[k] = greutate[i];
k++; i++;
}
while (j <= dr) {
vTemp[k] = valoare[j];
gTemp[k] = greutate[j];
k++; j++;
}
for (int p = st; p <= dr; p++) {
valoare[p] = vTemp[p];
greutate[p] = gTemp[p];
}
}
void sorteaza(int st, int dr) {
if (st < dr) {
int mij = (st + dr) / 2;
sorteaza(st, mij);
sorteaza(mij + 1, dr);
interclaseaza(st, mij, dr);
}
}
int main() {
int n, g;
cin >> n >> g;
for (int i = 1; i <= n; i++) {
cin >> valoare[i] >> greutate[i];
}
sorteaza(1, n);
double castig = 0;
for (int i = 1; i <= n && g > 0; i++) {
if (greutate[i] <= g) {
castig += valoare[i];
g -= greutate[i];
} else {
castig += valoare[i] * 1.0 * g / greutate[i];
g = 0;
}
}
cout << fixed << setprecision(2) << castig << endl;
return 0;
}
Ce învățăm: programul îmbină cele două metode: interclasarea (D&I) ordonează obiectele, iar umplerea (Greedy) maximizează valoarea. Pentru exemplul dat, câștigul este 240.00.
PbInfo - Verificarea planificării spectacolelor
Enunț:
Cerință: Se citesc n spectacole (început, sfârșit). Folosind metoda Greedy, se determină numărul maxim de spectacole compatibile. Apoi, o funcție recursivă de tip Divide et impera verifică soluția, iar programul afișează mesajul „Corect" dacă verificarea trece.
Date de intrare:
Programul citește n, apoi n perechi început sfârșit.
Date de ieșire:
Programul va afișa numărul de spectacole alese și mesajul „Corect".
Restricții și precizări:
1 ≤ n ≤ 100; 1 ≤ început < sfârșit ≤ 1440; verificarea se face cu o funcție recursivă de tip D&I.
Exemplu:
Intrare:
4 1 3 2 5 4 6 6 8
Ieșire:
3 spectacole Corect
Cum gândim soluția:
- Sortăm spectacolele după sfârșit și selectăm greedy
- Definim verifica(st, dr) recursiv, cu granița compatibil(mij, mij + 1)
- Afișăm numărul și mesajul de confirmare
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int inceput[101], sfarsit[101];
int alese[101];
int nrAlese = 0;
void sorteaza(int n) {
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (sfarsit[i] > sfarsit[j]) {
int aux = sfarsit[i];
sfarsit[i] = sfarsit[j];
sfarsit[j] = aux;
aux = inceput[i];
inceput[i] = inceput[j];
inceput[j] = aux;
}
}
}
}
void selecteazaGreedy(int n) {
alese[1] = 1;
nrAlese = 1;
int ultimul = sfarsit[1];
for (int i = 2; i <= n; i++) {
if (inceput[i] >= ultimul) {
nrAlese++;
alese[nrAlese] = i;
ultimul = sfarsit[i];
}
}
}
bool compatibil(int a, int b) {
return sfarsit[alese[a]] <= inceput[alese[b]];
}
bool verifica(int st, int dr) {
if (st >= dr) {
return true;
}
int mij = (st + dr) / 2;
if (!verifica(st, mij)) {
return false;
}
if (!verifica(mij + 1, dr)) {
return false;
}
return compatibil(mij, mij + 1);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> inceput[i] >> sfarsit[i];
}
sorteaza(n);
selecteazaGreedy(n);
if (verifica(1, nrAlese)) {
cout << nrAlese << " spectacole" << endl;
cout << "Corect" << endl;
}
return 0;
}
Ce învățăm: pentru exemplul dat, spectacolele alese sunt (1,3), (4,6), (6,8), deci 3 spectacole, iar verificarea D&I confirmă compatibilitatea granițelor.
Exercițiul Practic: probleme combinate D&I și Greedy
Sarcini de lucru
Rezolvă sarcinile de mai jos pentru a exersa îmbinarea celor două metode
Sarcina 1: Rucsac fracționar complet
Cerință: Scrie programul C++ complet pentru rucsacul fracționar combinat: interclasare pentru sortarea după eficiență, apoi umplere greedy. Verifică pe exemplul n = 3, g = 10, obiectele (60, 10), (100, 20), (120, 30).
Soluție pentru Sarcina 1:
#include <iostream>
#include <iomanip>
using namespace std;
int valoare[100001], greutate[100001];
int vTemp[100001], gTemp[100001];
bool maiEficient(int i, int j) {
return valoare[i] * 1LL * greutate[j] > valoare[j] * 1LL * greutate[i];
}
void interclaseaza(int st, int mij, int dr) {
int i = st, j = mij + 1, k = st;
while (i <= mij && j <= dr) {
if (maiEficient(i, j)) {
vTemp[k] = valoare[i];
gTemp[k] = greutate[i];
k++; i++;
} else {
vTemp[k] = valoare[j];
gTemp[k] = greutate[j];
k++; j++;
}
}
while (i <= mij) {
vTemp[k] = valoare[i];
gTemp[k] = greutate[i];
k++; i++;
}
while (j <= dr) {
vTemp[k] = valoare[j];
gTemp[k] = greutate[j];
k++; j++;
}
for (int p = st; p <= dr; p++) {
valoare[p] = vTemp[p];
greutate[p] = gTemp[p];
}
}
void sorteaza(int st, int dr) {
if (st < dr) {
int mij = (st + dr) / 2;
sorteaza(st, mij);
sorteaza(mij + 1, dr);
interclaseaza(st, mij, dr);
}
}
int main() {
int n, g;
cin >> n >> g;
for (int i = 1; i <= n; i++) {
cin >> valoare[i] >> greutate[i];
}
sorteaza(1, n);
double castig = 0;
for (int i = 1; i <= n && g > 0; i++) {
if (greutate[i] <= g) {
castig += valoare[i];
g -= greutate[i];
} else {
castig += valoare[i] * 1.0 * g / greutate[i];
g = 0;
}
}
cout << fixed << setprecision(2) << castig << endl;
return 0;
}
Verifică: toate obiectele au eficiența 6; luăm primul întreg (60), apoi două treimi din al doilea, total 240.00. Dacă schimbi greutatea celui de-al doilea obiect la 15, eficiențele se schimbă și ordinea la fel.
Sarcina 2: Spectacole cu verificare D&I
Cerință: Scrie programul C++ complet pentru problema spectacolelor cu verificare prin Divide et impera. Testează pe spectacolele (1, 3), (2, 5), (4, 6), (6, 8) și apoi pe un caz cu suprapunere forțată, pentru a observa comportarea funcției verifica.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int inceput[101], sfarsit[101];
int alese[101];
int nrAlese = 0;
void sorteaza(int n) {
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (sfarsit[i] > sfarsit[j]) {
int aux = sfarsit[i];
sfarsit[i] = sfarsit[j];
sfarsit[j] = aux;
aux = inceput[i];
inceput[i] = inceput[j];
inceput[j] = aux;
}
}
}
}
void selecteazaGreedy(int n) {
alese[1] = 1;
nrAlese = 1;
int ultimul = sfarsit[1];
for (int i = 2; i <= n; i++) {
if (inceput[i] >= ultimul) {
nrAlese++;
alese[nrAlese] = i;
ultimul = sfarsit[i];
}
}
}
bool compatibil(int a, int b) {
return sfarsit[alese[a]] <= inceput[alese[b]];
}
bool verifica(int st, int dr) {
if (st >= dr) {
return true;
}
int mij = (st + dr) / 2;
if (!verifica(st, mij)) {
return false;
}
if (!verifica(mij + 1, dr)) {
return false;
}
return compatibil(mij, mij + 1);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> inceput[i] >> sfarsit[i];
}
sorteaza(n);
selecteazaGreedy(n);
if (verifica(1, nrAlese)) {
cout << "Soluția greedy este corectă: " << nrAlese << " spectacole" << endl;
} else {
cout << "Eroare în selecție" << endl;
}
return 0;
}
Verifică: pentru (1,3), (2,5), (4,6), (6,8) rezultatul este „Soluția greedy este corectă: 3 spectacole". Urmărește pe hârtie apelurile verifica(1, 2) și verifica(1, 3) pentru a înțelege descompunerea.
Scrie pe caiet - Probleme combinate D&I și Greedy
Titlul lecției
- Ora 12: Probleme combinate D&I și Greedy
Definiția lecției
O problemă combinată folosește ambele metode ale modulului, fiecare pe partea ei: Divide et impera organizează datele (sortare prin interclasare, căutare binară, prelucrare pe intervale) sau verifică o soluție, iar Greedy ia deciziile pe datele deja pregătite. În lecție se rezolvă două exemple: rucsacul fracționar cu interclasare după eficiență și umplere greedy, și problema spectacolelor cu selecție greedy urmată de verificarea compatibilității printr-o funcție recursivă D&I. Verificarea recursivă nu parcurge toate perechile, ci doar granițele dintre jumătăți, rămânând în O(n log n) și fiind corectă pe lista ordonată după sfârșit. La oral, problema se prezintă ca o conductă: pregătire D&I, decizie Greedy, verificare D&I. Identificarea celor două etape ale enunțului este primul pas spre o soluție completă.
Definiții esențiale
- Problemă combinată: problemă care folosește Divide et impera pentru pregătirea sau verificarea datelor și Greedy pentru alegerea optimului local.
- Rolul D&I: sortare prin interclasare (O(n log n)), căutare binară (O(log n)), prelucrare sau verificare pe intervale.
- Rolul Greedy: construirea soluției pas cu pas, cu criterii locale (eficiență, sfârșit cel mai devreme, monedă maximă).
- Verificare D&I: funcție recursivă care confirmă o proprietate pe întregul șir, verificând jumătățile și granițele.
Algoritmul cheie - pseudocod
- Rucsac combinat: merge sort după eficiență, apoi umplere greedy cu fracțiune finală.
- Verificare D&I:
verifica(st, dr)— caz de bazăst >= dr; altfel verifică jumătățile și granițacompatibil(mij, mij + 1).
Algoritmul cheie - cod C++
- Interclasarea mută perechile (valoare, greutate) împreună; comparația folosește înmulțiri încrucișate cu 1LL.
- Umplerea greedy: întreg dacă încape, fracțiune
valoare[i] * 1.0 * g / greutate[i]altfel. - Verificarea: funcție recursivă
bool verifica(int st, int dr)pe lista spectacolelor alese.
Greșeli comune de evitat
- Folosirea unei singure metode când enunțul cere două etape distincte.
- Verificarea tuturor perechilor (O(n)) în loc de verificarea granițelor (O(n log n)).
- Verificarea pe spectacole nesortate: proprietatea granițelor ține doar pe lista ordonată după sfârșit.
- Uitarea condiției de oprire
g == 0la umplerea rucsacului.
Sfaturi practice și trucuri
- Identifică întâi cele două etape ale enunțului și scrie-le separat, apoi lege-le.
- La verificarea D&I, testează mai întâi cazurile mici: un spectacol (adevărat), două spectacole compatibile, două incompatibile.
- La rucsac, verifică întotdeauna că sortarea a reordonat corect perechile (valoare, greutate).
- La oral, prezintă problema ca pe o conductă: pregătire D&I, decizie Greedy, verificare D&I.
Exemplu practic
După ce a ales spectacolele cu strategia greedy, un elev verifică, cu o funcție recursivă, că lista finală nu conține suprapuneri: fiecare jumătate trebuie să fie validă, iar granița dintre ele (mij, mij + 1) trebuie să respecte compatibilitatea. Pentru spectacolele alese (1, 3), (4, 6), (6, 8), funcția de mai jos întoarce adevărat (3 spectacole corecte):
bool compatibil(int a, int b) {
return sfarsit[alese[a]] <= inceput[alese[b]];
}
bool verifica(int st, int dr) {
if (st >= dr) {
return true;
}
int mij = (st + dr) / 2;
if (!verifica(st, mij)) {
return false;
}
if (!verifica(mij + 1, dr)) {
return false;
}
return compatibil(mij, mij + 1);
}