Ce vei învăța astăzi?
După această lecție vei putea să sortezi eficient obiectele unui rucsac fracționar folosind sortarea prin interclasare și să rezolvi extinderea problemei platoului: tăierea unei plăci în pătrate cât mai mari, repetat, până la epuizare.
Rucsacul fracționar: recapitulare și criteriul eficienței
Definiție: La rucsacul fracționar se dau n obiecte cu valoare și greutate și o capacitate g. Obiectele pot fi luate și parțial. Eficiența unui obiect este raportul valoare / greutate: valoarea adusă de o unitate de greutate. Strategia greedy alege obiectele în ordinea descrescătoare a eficienței, umplând cu fiecare cât mai mult posibil.
Analogie: selecția fructelor de la piață
Un comerciant are un coș cu o capacitate limitată și alege între mai multe lăzi de fructe. Nu alege după valoarea totală a lăzii, ci după prețul pe kilogram (valoare / greutate): lada de vișine cu 12 lei pe kilogram este preferată unei lăzi de piersici cu 8 lei pe kilogram, chiar dacă piersicile valorează mai mult la total. Umple coșul cu cel mai scump fruct pe kilogram, apoi trece la următorul, și poate lua și jumătate de ladă dacă nu mai încape totul.
Observă: compararea eficiențelor se face fără împărțire, cu înmulțiri încrucișate: obiectul i este mai eficient decât j dacă valoare[i] * greutate[j] > valoare[j] * greutate[i].
Rucsacul fracționar cu sortare prin interclasare
Pentru n mare, sortarea prin selecție (O(n)) devine prea lentă. Folosim sortarea prin interclasare (merge sort), de complexitate O(n log n), adaptată pentru a muta împreună valoarea și greutatea fiecărui obiect. După sortare, umplem rucsacul exact ca la ora 8: obiectul întreg dacă încape, fracțiune altfel.
#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: funcția maiEficient(i, j) compară eficiențele fără împărțire; interclasarea mută perechile (valoare, greutate) împreună, iar umplerea rămâne identică cu varianta de la ora 8. Complexitatea totală devine O(n log n).
Problema platoului extins: pătrate cât mai mari, repetat
Definiție: Avem o placă dreptunghiulară L × W. La fiecare pas tăiem din placă cât mai multe pătrate cu latura egală cu latura mai mică a plăcii curente, apoi continuăm cu restul. Se cere numărul total de pătrate obținute până când placa este epuizată. Strategia greedy „cea mai mare latură posibilă, cât mai des" este optimă și seamănă cu algoritmul lui Euclid pentru cel mai mare divizor comun.
Exemplu: placă 10 × 6
- L = 10, W = 6: tăiem
10 / 6 = 1pătrat de 6 × 6; restul are dimensiunile 4 × 6 - L = 4, W = 6: tăiem
6 / 4 = 1pătrat de 4 × 4; restul are dimensiunile 4 × 2 - L = 4, W = 2: tăiem
4 / 2 = 2pătrate de 2 × 2; placa se epuizează
Total: 4 pătrate (unul de 6 × 6, unul de 4 × 4 și două de 2 × 2).
Observă: dacă L și W au un divizor comun mare, numărul de pătrate este mic; dacă sunt prime între ele, ultimele pătrate au latura 1. Algoritmul este foarte rapid: la fiecare pas o dimensiune scade cel puțin la jumătate.
#include <iostream>
using namespace std;
int main() {
int L, W;
cin >> L >> W;
int nr = 0;
while (L > 0 && W > 0) {
if (L > W) {
nr += L / W;
L %= W;
} else {
nr += W / L;
W %= L;
}
}
cout << nr << endl;
return 0;
}
Ce învățăm: tăiem întotdeauna pătrate cu latura egală cu dimensiunea mai mică, cât de multe încap, apoi trecem la rest. Divizarea cu rest amintește de algoritmul lui Euclid, iar numărul de pași este foarte mic.
Aprofundare
Demonstrația corectitudinii rucsacului fracționar: dacă o soluție nu alege obiectul cu eficiența maximă, putem înlocui o parte din greutatea ei cu acel obiect și valoarea totală crește sau rămâne egală. Repetând înlocuirea, ajungem la soluția greedy, deci soluția greedy este optimă. Aceasta este demonstrația „de schimb", specifică metodei Greedy, și trebuie formulată corect la proba orală.
De ce merge sort, nu sortare prin selecție: pentru n = 100000 de obiecte, sortarea prin selecție face aproximativ 10 miliarde de operații, în timp ce merge sort face aproximativ 1,7 milioane. La problemele de concurs cu n mare, alegerea sortării determină singură acceptarea soluției.
Înmulțirile cu 1LL: eficiențele pot ajunge la 10⁹, iar produsele valoare[i] * greutate[j] pot depăși 2 miliarde. Multiplicatorul 1LL forțează calculul în long long, evitând depășirea tipului int.
Platoul extins și cel clasic: la ora 8, placa se taie în pătrate cu o latură fixată l, iar răspunsul este (L / l) * (W / l). Aici latura pătratelor nu este fixată: tăiem mereu pătratele cât mai mari posibil, repetat. Ambele variante sunt greedy, dar criteriile locale diferă; recunoașterea variantei cerute în enunț este jumătate din rezolvare.
Exemplu din viața reală: o firmă de ambalaje taie plăci de carton în pătrate de diferite dimensiuni, pentru a minimiza numărul de piese; un bucătar împarte o tavă dreptunghiulară de prăjitură în porții pătrate cât mai mari posibil, iar restul se porționează din nou. Ambele situații ilustrează alegerea greedy repetată: optimul local (cel mai mare pătrat posibil) duce la optimul global (număr minim de piese).
Exercițiu de completare
Completează enunțul despre rucsacul fracționar:
Criteriul greedy la rucsacul fracționar este sortarea obiectelor descrescător după ______ (valoare / greutate). Obiectele pot fi luate și ______. Pentru n mare, sortarea se face prin ______, în O(n log n). La compararea eficiențelor folosim ______ încrucișate, pentru a evita împărțirile reale.
Bancă de cuvinte:
Exercițiu de completare: platoul extins
Completează descrierea platoului extins:
La platoul extins, tăiem mereu pătrate cu latura egală cu dimensiunea ______ a plăcii. Numărul de pătrate de la un pas este L / ______ (când L este mai mare), iar dimensiunea rămasă se calculează cu L %= ______. Algoritmul amintește de algoritmul lui ______ pentru cel mai mare divizor comun.
Bancă de cuvinte:
Test de înțelegere
Test rapid - probleme avansate Greedy:
1. Pentru a compara eficiențele a două obiecte fără împărțire, verificăm:
2. La platoul extins, pentru placa 7 × 5, primul pas taie:
3. Complexitatea rucsacului fracționar cu sortare prin interclasare este:
PbInfo - Rucsac fracționar cu sortare eficientă
Enunț:
Cerință: Se dau n obiecte, fiecare cu valoare și greutate, și capacitatea g a unui rucsac. Obiectele pot fi luate și fracționar. Să se afișeze valoarea maximă care poate fi încărcată, cu două zecimale.
Date de intrare:
Programul citește n și g, apoi n perechi de forma 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; sortarea se face în O(n log n); se folosește metoda Greedy.
Exemplu:
Intrare:
3 10 60 10 100 20 120 30
Ieșire:
240.00
Cum gândim soluția:
- Sortăm obiectele descrescător după eficiență, prin interclasare
- Umplem rucsacul: obiect î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: pentru exemplul dat, toate obiectele au eficiența 6, deci luăm primul întreg (60) și două treimi din al doilea (66,66), total 240,00. Afișarea cu fixed << setprecision(2) respectă cerința cu două zecimale.
PbInfo - Platoul extins (pătrate maxime)
Enunț:
Cerință: Se dă o placă dreptunghiulară cu dimensiunile L și W. Placa se taie repetat în pătrate, alegând la fiecare pas cel mai mare pătrat posibil. Să se afișeze numărul total de pătrate obținute.
Date de intrare:
Programul citește de la tastatură numerele L și W.
Date de ieșire:
Programul va afișa numărul de pătrate.
Restricții și precizări:
1 ≤ L, W ≤ 1000000000; se folosește strategia greedy: cel mai mare pătrat posibil, repetat.
Exemplu:
Intrare:
10 6
Ieșire:
4
Cum gândim soluția:
- Cât timp placa nu este epuizată, tăiem cât mai multe pătrate cu latura dimensiunii mai mici
- Reducem dimensiunea mai mare cu restul împărțirii
- Afișăm numărul total de pătrate
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int L, W;
cin >> L >> W;
int nr = 0;
while (L > 0 && W > 0) {
if (L > W) {
nr += L / W;
L %= W;
} else {
nr += W / L;
W %= L;
}
}
cout << nr << endl;
return 0;
}
Ce învățăm: pentru 10 × 6, pașii sunt: un pătrat 6 × 6, un pătrat 4 × 4, două pătrate 2 × 2, total 4. Numărul de iterații este mic, deoarece fiecare rest este cel puțin înjumătățit la fiecare doi pași.
Exercițiul Practic: probleme avansate Greedy
Sarcini de lucru
Rezolvă sarcinile de mai jos pentru a consolida tehnicile greedy avansate
Sarcina 1: Rucsac fracționar cu afișarea fracțiunilor
Cerință: Scrie un program C++ care citește n, g și obiectele, sortează eficient și afișează valoarea maximă, dar și câte obiecte au fost luate întregi și cât a fost fracțiunea ultimului obiect (în procente, de exemplu 33.33%).
Soluție pentru Sarcina 1:
#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);
int intregi = 0;
double castig = 0, procent = 0;
for (int i = 1; i <= n && g > 0; i++) {
if (greutate[i] <= g) {
castig += valoare[i];
g -= greutate[i];
intregi++;
} else {
procent = g * 100.0 / greutate[i];
castig += valoare[i] * 1.0 * g / greutate[i];
g = 0;
}
}
cout << castig << endl;
cout << intregi << " obiecte intregi" << endl;
cout << procent << "% din ultimul obiect" << endl;
return 0;
}
Verifică: pentru n = 2, g = 5 și obiectele (10, 10) și (100, 20), eficiențele sunt 1 și 5; luăm obiectul al doilea fracționar, 25% din el (g / greutate = 5 / 20), iar câștigul este 25. Bucla se oprește la g = 0.
Sarcina 2: Platou extins cu afișarea pașilor
Cerință: Scrie un program C++ care citește L și W, tăie placa în pătrate cât mai mari și afișează, pentru fiecare pas, latura pătratelor și numărul lor, apoi totalul.
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int main() {
int L, W;
cin >> L >> W;
int nr = 0;
while (L > 0 && W > 0) {
int latura, cate;
if (L > W) {
latura = W;
cate = L / W;
L %= W;
} else {
latura = L;
cate = W / L;
W %= L;
}
nr += cate;
cout << cate << " patrate de " << latura << "x" << latura << endl;
}
cout << "Total: " << nr << endl;
return 0;
}
Verifică: pentru 10 × 6 se afișează: 1 pătrat de 6x6, 1 pătrat de 4x4, 2 pătrate de 2x2, Total: 4. Pentru 7 × 5: 1 pătrat de 5x5, 2 pătrate de 2x2, 1 pătrat de 1x1, total 4.
Scrie pe caiet - Probleme avansate Greedy
Titlul lecției
- Ora 11: Probleme avansate Greedy
Definiția lecției
Lecția combină greedy cu sortarea prin interclasare și extinde problema platoului. Rucsacul fracționar se rezolvă sortând obiectele descrescător după eficiență (valoare / greutate) cu merge sort, apoi umplând rucsacul: obiecte întregi cât încap și o fracțiune finală, totul rămânând în O(n log n). Compararea eficiențelor folosește înmulțiri încrucișate cu 1LL, pentru a evita împărțirile reale și erorile de rotunjire. Platoul extins cere numărul de pătrate obținute tăind repetat placa după dimensiunea mai mică: se adaugă L / W pătrate (sau W / L) și se continuă cu restul împărțirii, ca la algoritmul lui Euclid, în O(log L + log W) iterații. Dacă L == W, răspunsul este 1: un singur pătrat egal cu placa.
Definiții esențiale
- Eficiența unui obiect: raportul valoare / greutate; criteriul greedy la rucsacul fracționar este sortarea descrescătoare după eficiență.
- Rucsac fracționar: obiectele pot fi luate și parțial; ultimul obiect se ia fracționar, deci nu rămâne spațiu risipit.
- Platou extins: tăierea repetată a plăcii în pătrate cu latura egală cu dimensiunea mai mică, cât de multe încap, până la epuizare.
- Complexități: rucsac cu merge sort: O(n log n); platou extins: O(log L + log W) iterații.
Algoritmul cheie - pseudocod
- Rucsac: sortează după eficiență (interclasare), apoi umple cu obiecte întregi și fracțiune finală.
- Platou: cât timp L și W sunt pozitive, adaugă L / W (sau W / L) pătrate și reduce cu restul împărțirii.
Algoritmul cheie - cod C++
- Interclasare cu perechi (valoare, greutate) și comparație prin înmulțiri încrucișate cu 1LL.
- Umplere:
if (greutate[i] <= g)întreg, altfel fracțiuneavaloare[i] * 1.0 * g / greutate[i]. - Platou:
while (L > 0 && W > 0)cunr += L / W; L %= W;(și simetric).
Greșeli comune de evitat
- Compararea eficiențelor cu împărțire reală, cu erori de rotunjire; folosește înmulțirile încrucișate.
- Uitarea lui 1LL: produsele valoare * greutate depășesc tipul int.
- La platou, adunarea pătratelor pe fiecare direcție la pasul curent, dar uitarea actualizării dimensiunilor cu restul.
- Confundarea platoului extins (latură variabilă) cu cel clasic (latură fixată l).
Sfaturi practice și trucuri
- Verifică rucsacul pe exemplul clasic: n = 3, g = 10, obiecte (60,10), (100,20), (120,30) → 240.00.
- Pentru platou, urmărește pașii ca pe algoritmul lui Euclid; numărul de iterații este mic, deci programul rulează instant chiar și pentru valori de un miliard.
- Dacă L == W, răspunsul este 1: un singur pătrat egal cu placa.
- La oral, demonstrează rucsacul prin argumentul de schimb: orice soluție poate fi transformată în soluția greedy fără pierdere de valoare.
Exemplu practic
Un tâmplar taie o scândură de 168 × 64 cm în pătrate cât mai mari, repetat, până la epuizare: 168 / 64 = 2 pătrate de 64, rămân 40 × 64; apoi 64 / 40 = 1 pătrat de 40, rămân 40 × 24; apoi 40 / 24 = 1 pătrat de 24, rămân 24 × 16; apoi 24 / 16 = 1 pătrat de 16, rămân 16 × 8; apoi 16 / 8 = 2 pătrate de 8. În total 7 pătrate. Bucla de mai jos implementează tăierea repetată:
int nr = 0;
while (L > 0 && W > 0) {
if (L >= W) {
nr += L / W;
L %= W;
} else {
nr += W / L;
W %= L;
}
}
cout << nr << endl;