Ce vei învăța astăzi?
După această lecție vei aplica metoda Greedy la două probleme clasice: rucsacul fracționar (obiecte care pot fi tăiate) și problema platoului (tăierea unei plăci în bucăți egale).
Rucsacul fracționar
Cerință: Avem n obiecte, fiecare cu o greutate și o valoare, și un rucsac cu capacitatea G. Obiectele pot fi tăiate (luăm și fracțiuni). Să se aleagă obiectele (sau părți din ele) astfel încât valoarea totală încărcată să fie maximă.
Strategia greedy: sortăm obiectele după eficiență (valoare / greutate) descrescător; luăm întotdeauna, dacă încape, obiectul întreg, altfel doar fracțiunea care mai încape.
Analogie: cumpărături în piață
Ai un buget mic și vrei să iei fructe care „se merită" cel mai mult la kilogram. Te uiți întâi la produsul cu cel mai bun raport calitate-preț pe kilogram, îl iei cât ai nevoie, apoi treci la următorul. Astfel îți folosești bugetul cât mai eficient.
Exemplu: capacitate 10
| Obiect | Valoare | Greutate | Eficiență (v/g) |
|---|---|---|---|
| 1 | 60 | 3 | 20 |
| 2 | 100 | 5 | 20 |
| 3 | 20 | 2 | 10 |
Luăm obiectul 1 (60, greutate rămasă 7), obiectul 2 (100, greutate rămasă 2), apoi din obiectul 3 luăm doar 2 unități din cele 2: 20. Total: 180.
Rucsacul fracționar în C++
Comparăm eficiențele fără împărțire, cu înmulțiri încrucișate (BAC-friendly): obiectul i este mai eficient decât j dacă valoare[i] * greutate[j] > valoare[j] * greutate[i].
#include <iostream>
using namespace std;
int valoare[101], greutate[101];
void sorteaza(int n) {
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (valoare[i] * greutate[j] < valoare[j] * greutate[i]) {
int aux = valoare[i];
valoare[i] = valoare[j];
valoare[j] = aux;
aux = greutate[i];
greutate[i] = greutate[j];
greutate[j] = aux;
}
}
}
}
int main() {
int n, g;
cin >> n >> g;
for (int i = 1; i <= n; i++) {
cin >> valoare[i] >> greutate[i];
}
sorteaza(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: dacă obiectul nu încape întreg, luăm doar fracțiunea g / greutate[i] din valoarea lui; bucla se oprește când rucsacul este plin (g == 0).
Problema platoului
Cerință: Avem o placă dreptunghiulară cu dimensiunile L × W și vrem să tăiem din ea cât mai multe plăci pătrate cu latura l. Numărul de pătrate este (L / l) * (W / l).
Strategia greedy: umplem placa pe lungime cu L / l pătrate și pe lățime cu W / l pătrate; fiecare pas local („umple cât poți pe fiecare direcție") dă numărul maxim.
Exemplu: placă 10 × 6, pătrate cu latura 2
Pe lungime încap 10 / 2 = 5 pătrate, pe lățime 6 / 2 = 3 pătrate, deci 5 * 3 = 15 pătrate. Restul de placă rămâne nefolosit (bucățile trebuie să fie întregi).
#include <iostream>
using namespace std;
int main() {
int L, W, l;
cin >> L >> W >> l;
int nr = (L / l) * (W / l);
cout << nr << endl;
return 0;
}
Ce învățăm: împărțirea întreagă L / l arată câte pătrate încap pe o direcție; restul rămas nu poate forma un pătrat întreg, deci nu se numără.
Exercițiu de completare
Completează descrierea rucsacului fracționar:
În rucsacul fracționar sortăm obiectele descrescător după ______ (valoare / ______). Luăm obiectul ______ dacă încape, altfel luăm doar o ______ din el.
Bancă de cuvinte:
Exercițiu de completare: problema platoului
Completează descrierea problemei platoului:
Numărul de bucăți de latură l dintr-un dreptunghi L × W este (L / l) * (W / ______); restul de placă rămâne ______ deoarece bucățile trebuie să fie ______.
Bancă de cuvinte:
Test de înțelegere
Test rapid - probleme Greedy aplicative:
1. La rucsacul fracționar, obiectele se sortează după:
2. Diferența rucsacului fracționar față de cel 0/1 este:
3. La problema platoului, numărul de pătrate de latură l se calculează cu:
1.0 * capacitate înainte de împărțire; fără 1.0, împărțirea întreagă dă 0 pentru fracțiuni și rezultatul este greșit.Aprofundare
De ce rucsacul fracționar este rezolvabil greedy, iar cel întreg nu: atunci când obiectele pot fi tăiate, ultimul obiect adăugat poate fi luat „parțial", deci nu rămâne niciodată spațiu risipit; alegerea locală a obiectului cu cea mai mare eficiență este mereu optimă. La rucsacul întreg (0-1), spațiul rămas după alegeri poate rămâne nefolosit, iar greedy-ul poate rata optimul, de aceea acea problemă se rezolvă cu programare dinamică.
Comparația eficiențelor fără împărțire: compararea valoare[i] / greutate[i] cu numere reale poate aduce erori de rotunjire. Varianta BAC-friendly folosește înmulțiri încrucișate: obiectul i este mai eficient decât j dacă valoare[i] * greutate[j] > valoare[j] * greutate[i], calcul realizat integral cu numere întregi.
Cazuri particulare la rucsac: dacă un singur obiect are greutatea mai mare decât capacitatea, se ia doar fracțiunea lui; dacă suma tuturor greutăților este mai mică decât capacitatea, se iau toate obiectele întregi; dacă două obiecte au aceeași eficiență, orice ordine între ele este corectă. Bucla se oprește când capacitatea rămasă devine 0.
Problema platoului, generalizată: dacă placa este tăiată în pătrate cu latura l, numărul maxim este (L / l) * (W / l), unde împărțirile sunt întregi. Strategia greedy umple pe lungime cu cât mai multe pătrate, apoi pe lățime; restul de placă rămâne nefolosit, pentru că bucățile trebuie să fie pătrate întregi. Dacă l nu divide L sau W, restul este o fâșie care nu poate fi folosită.
Exemplu din viața reală: un fermier care vrea să umple un siloz cu grâu, porumb și soia alege întâi produsul cu cel mai bun preț pe kilogram, umplând cu el cât poate, apoi trece la următorul. Un geamgiu care taie o foaie de sticlă în pătrate identice calculează câte pătrate încap pe fiecare direcție. Ambele situații sunt aplicații directe ale alegerii optime locale.
PbInfo - Rucsac (fracționar)
Enunț:
Cerință: Se dau n obiecte (valoare și greutate) și capacitatea G a unui rucsac. Obiectele pot fi tăiate. Să se afișeze valoarea maximă care poate fi încărcată.
Date de intrare:
Programul citește n și G, apoi n perechi: valoarea și greutatea fiecărui obiect.
Date de ieșire:
Programul va afișa valoarea maximă (număr real).
Restricții și precizări:
1 ≤ n ≤ 100; valorile și greutățile sunt numere naturale; se folosește metoda Greedy, sortare după eficiență.
Exemplu:
Intrare:
3 10 60 3 100 5 20 2
Ieșire:
180
Cum gândim soluția:
- Sortăm obiectele după eficiență, descrescător
- Luăm obiectul întreg dacă încape, altfel fracțiunea necesară
- Adunăm valorile și afișăm rezultatul
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int valoare[101], greutate[101];
void sorteaza(int n) {
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (valoare[i] * greutate[j] < valoare[j] * greutate[i]) {
int aux = valoare[i];
valoare[i] = valoare[j];
valoare[j] = aux;
aux = greutate[i];
greutate[i] = greutate[j];
greutate[j] = aux;
}
}
}
}
int main() {
int n, g;
cin >> n >> g;
for (int i = 1; i <= n; i++) {
cin >> valoare[i] >> greutate[i];
}
sorteaza(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: comparăm eficiențele fără împărțire (înmulțiri încrucișate) pentru a evita erorile de tip real la sortare.
PbInfo - Platoul
Enunț:
Cerință: Se dă o placă dreptunghiulară cu dimensiunile L și W. Să se afișeze numărul maxim de plăci pătrate cu latura l care pot fi tăiate din ea.
Date de intrare:
Programul citește de la tastatură numerele L, W și l.
Date de ieșire:
Programul va afișa numărul maxim de pătrate.
Restricții și precizări:
1 ≤ l ≤ L, W ≤ 1000; pătratele nu pot fi combinate din resturi, fiecare pătrat trebuie să fie întreg.
Exemplu:
Intrare:
10 6 2
Ieșire:
15
Cum gândim soluția:
- Calculăm câte pătrate încap pe lungime:
L / l - Calculăm câte pătrate încap pe lățime:
W / l - Înmulțim cele două valori
Scrie soluția în C++:
Soluție corectă:
#include <iostream>
using namespace std;
int main() {
int L, W, l;
cin >> L >> W >> l;
int nr = (L / l) * (W / l);
cout << nr << endl;
return 0;
}
Ce învățăm: împărțirea întreagă dă numărul de pătrate întregi pe fiecare direcție; resturile nu se pot combina.
Exercițiul Practic: aplicații Greedy
Sarcini de lucru
Rezolvă sarcinile de mai jos pentru a aplica metoda Greedy în situații noi
Sarcina 1: Cantitățile din rucsac
Cerință: Scrie un program care afișează, pentru fiecare obiect luat în ordinea eficienței, numărul de ordine inițial și cantitatea luată („întreg" sau „x din greutate").
Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;
int valoare[101], greutate[101], indice[101];
void sorteaza(int n) {
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
if (valoare[i] * greutate[j] < valoare[j] * greutate[i]) {
int aux = valoare[i];
valoare[i] = valoare[j];
valoare[j] = aux;
aux = greutate[i];
greutate[i] = greutate[j];
greutate[j] = aux;
aux = indice[i];
indice[i] = indice[j];
indice[j] = aux;
}
}
}
}
int main() {
int n, g;
cin >> n >> g;
for (int i = 1; i <= n; i++) {
cin >> valoare[i] >> greutate[i];
indice[i] = i;
}
sorteaza(n);
for (int i = 1; i <= n && g > 0; i++) {
if (greutate[i] <= g) {
cout << "Obiectul " << indice[i] << ": intreg" << endl;
g -= greutate[i];
} else {
cout << "Obiectul " << indice[i] << ": " << g << " din " << greutate[i] << endl;
g = 0;
}
}
return 0;
}
Verifică: pentru exemplul din teorie (capacitate 10), afișăm obiectele 1 și 2 ca „intreg", iar obiectul 3 ca „2 din 2". Păstrăm numărul inițial în tabloul indice.
Sarcina 2: Platou cu rest de arie
Cerință: Scrie un program care afișează numărul de pătrate tăiate și aria nefolosită (aria plăcii minus aria pătratelor).
Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;
int main() {
int L, W, l;
cin >> L >> W >> l;
int bucati = (L / l) * (W / l);
int folosit = bucati * l * l;
int total = L * W;
cout << bucati << " " << total - folosit << endl;
return 0;
}
Verifică: pentru placa 10 × 6 și latura 2, obținem 15 pătrate, arie folosită 15 · 4 = 60, arie totală 60, rest 0. Pentru 10 × 5 și latura 2: (5 · 2) = 10 pătrate, arie 40, total 50, rest 10.
Scrie pe caiet - Probleme Greedy aplicative
Titlul lecției
- Ora 8: Probleme Greedy aplicative
Definiția lecției
Rucsacul fracționar cere valoarea totală maximă care încape într-un rucsac de capacitate g, putându-se lua obiecte și parțial. Criteriul greedy este eficiența (valoarea adusă de o unitate de greutate): obiectele se sortează descrescător după eficiență și se iau în această ordine, întregi dacă încap, iar ultimul obiect se ia fracționar. Compararea eficiențelor se face fără împărțire, cu înmulțiri încrucișate, ca să nu apară erori de rotunjire. Problema platoului cere numărul maxim de pătrate cu latura l tăiate dintr-o placă L × W: (L / l) * (W / l), cu împărțiri întregi. Ambele probleme sunt aplicații directe ale metodei Greedy, frecvente la Bacalaureat și la concursuri.
Definiții esențiale
- Rucsacul fracționar: se dau n obiecte cu valoare și greutate și o capacitate g; se cere valoarea maximă care încape, putându-se lua și fracțiuni din obiecte.
- Eficiența unui obiect: raportul
valoare / greutate(valoare pe kilogram); criteriul greedy este sortarea descrescătoare după eficiență. - Fracțiunea: dacă obiectul curent nu încape întreg, se ia fracțiunea
g / greutate[i]din valoarea lui. - Problema platoului: numărul maxim de pătrate cu latura l tăiate dintr-o placă L × W este
(L / l) * (W / l), cu împărțiri întregi.
Algoritmul cheie - pseudocod
- Sortează obiectele descrescător după eficiență.
- Pentru fiecare obiect, cât timp mai e loc: ia-l întreg dacă încape, altfel ia fracțiunea și oprește-te.
- Adună valorile în
castigși afișează.
Algoritmul cheie - cod C++
- Tablouri globale
int valoare[101], greutate[101]; - Sortare cu înmulțiri încrucișate:
valoare[i] * greutate[j] < valoare[j] * greutate[i]→ interschimbă. - Bucla de umplere:
if (greutate[i] <= g) { castig += valoare[i]; g -= greutate[i]; } else { castig += valoare[i] * 1.0 * g / greutate[i]; g = 0; } - Rezultatul se afișează ca număr real (
double castig).
Greșeli comune de evitat
- Compararea eficiențelor cu împărțire reală și erori de rotunjire; folosește înmulțirile încrucișate.
- Uitarea condiției
g > 0în buclă: după umplerea rucsacului nu mai are sens să continui. - Calcularea fracțiunii fără
1.0:valoare[i] * g / greutate[i]cu întregi dă rezultat greșit. - La platou, împărțirea reală în loc de cea întreagă: 7 / 2 nu este 3.5 pătrate, ci 3.
Sfaturi practice și trucuri
- Verifică manual pe exemplul cu capacitate 50 și obiectele (valoare, greutate) = (60, 10), (100, 20), (120, 30): rezultatul este 240.
- La platou, reține formula
(L / l) * (W / l); nu aduna pătratele de pe fiecare direcție, ci înmulțește-le. - Distinge clar rucsacul fracționar (greedy corect) de cel întreg (greedy poate eșua).
- La oral, justifică alegerea obiectului cu eficiența maximă: „aduce cea mai multă valoare pe unitatea de greutate".
Exemplu practic
Un muncitor încarcă un camion cu capacitate de 50 de tone, având trei materiale cu perechile (valoare, greutate) = (60, 10), (100, 20) și (120, 30). Eficiențele sunt 6, 5 și 4, deci ia întregi primele două materiale (160 de lei, 30 de tone) și 20 din cele 30 de tone ale ultimului, obținând 160 + 120 · 20 / 30 = 240 de lei. Bucla de umplere greedy este cea de mai jos:
if (greutate[i] <= g) {
castig += valoare[i];
g -= greutate[i];
} else {
castig += valoare[i] * 1.0 * g / greutate[i];
g = 0;
}