Metoda Greedy
Învață tehnica Greedy în C++ fără STL, cu exemple practice și rezolvări complete pentru problemele clasice de algoritmică.
Începe TutorialulCe este Metoda Greedy?
O tehnică algoritmică fundamentală bazată pe alegeri locale optime pentru a ajunge la o soluție globală.
Alegere Locală Optimă
La fiecare pas, algoritmul alege cea mai bună opțiune disponibilă în acel moment, fără a reconsidera deciziile anterioare.
Eficiență
Algoritmii greedy sunt de obicei foarte eficienți, cu complexitate polinomială, deoarece nu explorează toate posibilitățile.
Limitări
Nu garantează întotdeauna soluția optimă globală. Funcționează doar pentru probleme cu proprietatea greedy.
Principiul Greedy - Vizualizare
Imaginează-ți că ai de ales monede pentru a forma suma 47, din monedele: 25, 10, 5, 1. Greedy alege întotdeauna cea mai mare monedă posibilă:
Rezultat: 25 + 10 + 10 + 1 + 1 = 47 (4 monede)
Structura Algoritmului Greedy
Pașii fundamentali pentru implementarea unui algoritm greedy corect.
Definește Criteriul de Selecție
Stabilește regula după care vei alege elementul optim la fiecare pas. Aceasta este cheia succesului algoritmului.
Sortează Datele (dacă e necesar)
Multe probleme greedy necesită sortarea elementelor după criteriul stabilit pentru a facilita selecția.
Iterează și Selectează
Parcurge elementele și selectează-le pe cele care respectă criteriul și pot fi adăugate la soluție.
Verifică Fezabilitatea
Asigură-te că elementul selectat poate fi adăugat fără a încălca restricțiile problemei.
// Șablon general pentru algoritmul Greedy
#include <iostream>
using namespace std;
// Structură pentru reprezentarea elementelor
struct Element {
int valoare;
int criteriu; // criteriul de sortare/selectie
};
// Functie de sortare (fara STL - folosim bubble sort simplu)
void sorteaza(Element arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j].criteriu > arr[j + 1].criteriu) {
Element temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Functia principala Greedy
void greedy(Element arr[], int n) {
// Pasul 1: Sorteaza dupa criteriu
sorteaza(arr, n);
// Pasul 2: Selecteaza elementele
for (int i = 0; i < n; i++) {
if (/* element fezabil */ true) {
// Adauga la solutie
cout << "Selectat: " << arr[i].valoare << endl;
}
}
}Probleme Clasice Rezolvate
Exemple complete cu explicații detaliate și cod funcțional în C++ fără STL.
1. Selecția Activităților
Selectează numărul maxim de activități care nu se suprapun.
Enunț
Se dau n activități, fiecare cu timpul de început și de sfârșit. Selectează numărul maxim de activități astfel încât nicio două activități selectate să nu se suprapună.
Exemplu
Intrare: n = 4
Activități: (1,3), (2,5), (3,6), (5,7)
Ieșire: 3 (activitățile 1, 3, 4 sau 1, 2, 4)
Strategia Greedy
Sortăm activitățile după timpul de sfârșit și selectăm mereu activitatea care se termină cel mai devreme și nu se suprapune cu ultima selectată.
#include <iostream>
using namespace std;
struct Activitate {
int start, sfarsit;
int index; // pentru a sti care activitate e
};
// Sortare dupa timpul de sfarsit
void sorteaza(Activitate a[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j].sfarsit > a[j + 1].sfarsit) {
Activitate temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}
int selecteazaActivitati(Activitate a[], int n, int selectate[]) {
sorteaza(a, n);
int count = 0;
int ultimulSfarsit = 0;
for (int i = 0; i < n; i++) {
// Daca activitatea curenta incepe dupa sau cand se termina ultima
if (a[i].start >= ultimulSfarsit) {
selectate[count] = a[i].index;
count++;
ultimulSfarsit = a[i].sfarsit;
}
}
return count;
}
int main() {
int n;
cout << "Numarul de activitati: ";
cin >> n;
Activitate activitati[100];
int selectate[100];
cout << "Introduceti start si sfarsit pentru fiecare activitate:\n";
for (int i = 0; i < n; i++) {
cin >> activitati[i].start >> activitati[i].sfarsit;
activitati[i].index = i + 1;
}
int numarSelectate = selecteazaActivitati(activitati, n, selectate);
cout << "\nNumar maxim de activitati: " << numarSelectate << endl;
cout << "Activitatile selectate: ";
for (int i = 0; i < numarSelectate; i++) {
cout << selectate[i] << " ";
}
cout << endl;
return 0;
}2. Problema Rucsacului Fracționar
Maximizează valoarea obiectelor într-un rucsac cu capacitate limitată.
Enunț
Se dau n obiecte, fiecare cu o greutate și o valoare. Ai un rucsac cu capacitate W. Poți lua fracțiuni din obiecte. Maximizează valoarea totală din rucsac.
Exemplu
Capacitate: W = 50
Obiecte: (greutate, valoare)
(10, 60), (20, 100), (30, 120)
Ieșire: 240 (tot obiectul 1, tot obiectul 2, 2/3 din obiectul 3)
Strategia Greedy
Sortăm obiectele descrescător după raportul valoare/greutate și le luăm în această ordine până umplem rucsacul.
#include <iostream>
using namespace std;
struct Obiect {
double greutate, valoare;
double raport; // valoare / greutate
int index;
};
// Sortare descrescatoare dupa raport
void sorteaza(Obiect ob[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (ob[j].raport < ob[j + 1].raport) {
Obiect temp = ob[j];
ob[j] = ob[j + 1];
ob[j + 1] = temp;
}
}
}
}
double rucsacFractionar(Obiect ob[], int n, double capacitate) {
// Calculeaza raportul pentru fiecare obiect
for (int i = 0; i < n; i++) {
ob[i].raport = ob[i].valoare / ob[i].greutate;
}
sorteaza(ob, n);
double valoareTotala = 0.0;
double capacitateRamasa = capacitate;
cout << "\nSelectie obiecte:\n";
for (int i = 0; i < n && capacitateRamasa > 0; i++) {
if (ob[i].greutate <= capacitateRamasa) {
// Luam obiectul intreg
valoareTotala += ob[i].valoare;
capacitateRamasa -= ob[i].greutate;
cout << "Obiect " << ob[i].index
<< ": 100% (valoare: " << ob[i].valoare << ")\n";
} else {
// Luam o fractiune
double fractiune = capacitateRamasa / ob[i].greutate;
valoareTotala += ob[i].valoare * fractiune;
cout << "Obiect " << ob[i].index
<< ": " << (fractiune * 100) << "% (valoare: "
<< (ob[i].valoare * fractiune) << ")\n";
capacitateRamasa = 0;
}
}
return valoareTotala;
}
int main() {
int n;
double capacitate;
cout << "Numarul de obiecte: ";
cin >> n;
cout << "Capacitatea rucsacului: ";
cin >> capacitate;
Obiect obiecte[100];
cout << "Introduceti greutatea si valoarea pentru fiecare obiect:\n";
for (int i = 0; i < n; i++) {
cin >> obiecte[i].greutate >> obiecte[i].valoare;
obiecte[i].index = i + 1;
}
double valoareMax = rucsacFractionar(obiecte, n, capacitate);
cout << "\nValoare maxima: " << valoareMax << endl;
return 0;
}3. Codificarea Huffman
Algoritm de compresie bazat pe frecvența caracterelor.
Enunț
Se dă un set de caractere cu frecvențele lor. Construiește un arbore Huffman pentru a genera coduri binare de lungime variabilă, astfel încât caracterele frecvente să aibă coduri scurte.
Exemplu
Caractere: a(5), b(9), c(12), d(13), e(16), f(45)
Coduri Huffman:
f: 0, c: 100, d: 101, a: 1100, b: 1101, e: 111
Strategia Greedy
Combinăm mereu cele două noduri cu frecvența minimă într-un nod părinte. Repetăm până obținem rădăcina arborelui.
#include <iostream>
using namespace std;
const int MAX_TREE_SIZE = 200;
struct NodHuffman {
char caracter;
int frecventa;
int stanga, dreapta; // indici in array, -1 daca nu exista
};
NodHuffman arbore[MAX_TREE_SIZE];
int dimensiuneArbore = 0;
// MinHeap simplu fara STL
int heap[MAX_TREE_SIZE]; // stocheaza indici in arbore
int heapSize = 0;
void heapifyUp(int idx) {
while (idx > 0) {
int parinte = (idx - 1) / 2;
if (arbore[heap[parinte]].frecventa > arbore[heap[idx]].frecventa) {
int temp = heap[parinte];
heap[parinte] = heap[idx];
heap[idx] = temp;
idx = parinte;
} else break;
}
}
void heapifyDown(int idx) {
while (2 * idx + 1 < heapSize) {
int stanga = 2 * idx + 1;
int dreapta = 2 * idx + 2;
int minim = stanga;
if (dreapta < heapSize &&
arbore[heap[dreapta]].frecventa < arbore[heap[stanga]].frecventa) {
minim = dreapta;
}
if (arbore[heap[idx]].frecventa > arbore[heap[minim]].frecventa) {
int temp = heap[idx];
heap[idx] = heap[minim];
heap[minim] = temp;
idx = minim;
} else break;
}
}
void inserareHeap(int indexNod) {
heap[heapSize] = indexNod;
heapifyUp(heapSize);
heapSize++;
}
int extragereMin() {
int minim = heap[0];
heap[0] = heap[heapSize - 1];
heapSize--;
heapifyDown(0);
return minim;
}
void afiseazaCoduri(int nod, char cod[], int lungime) {
if (nod == -1) return;
// Daca e frunza (nod cu caracter)
if (arbore[nod].stanga == -1 && arbore[nod].dreapta == -1) {
cod[lungime] = '\0';
cout << arbore[nod].caracter << ": " << cod << endl;
return;
}
// Parcurge stanga (adauga 0)
cod[lungime] = '0';
afiseazaCoduri(arbore[nod].stanga, cod, lungime + 1);
// Parcurge dreapta (adauga 1)
cod[lungime] = '1';
afiseazaCoduri(arbore[nod].dreapta, cod, lungime + 1);
}
int construiesteHuffman(char caractere[], int frecvente[], int n) {
// Creeaza noduri frunza
for (int i = 0; i < n; i++) {
arbore[dimensiuneArbore].caracter = caractere[i];
arbore[dimensiuneArbore].frecventa = frecvente[i];
arbore[dimensiuneArbore].stanga = -1;
arbore[dimensiuneArbore].dreapta = -1;
inserareHeap(dimensiuneArbore);
dimensiuneArbore++;
}
// Construieste arborele
while (heapSize > 1) {
// Extrage cele doua noduri cu frecventa minima
int stanga = extragereMin();
int dreapta = extragereMin();
// Creeaza nod parinte
arbore[dimensiuneArbore].caracter = '$'; // nod intern
arbore[dimensiuneArbore].frecventa =
arbore[stanga].frecventa + arbore[dreapta].frecventa;
arbore[dimensiuneArbore].stanga = stanga;
arbore[dimensiuneArbore].dreapta = dreapta;
inserareHeap(dimensiuneArbore);
dimensiuneArbore++;
}
// Returneaza radacina
return heap[0];
}
int main() {
int n;
cout << "Numarul de caractere: ";
cin >> n;
char caractere[100];
int frecvente[100];
cout << "Introduceti caracter si frecventa:\n";
for (int i = 0; i < n; i++) {
cin >> caractere[i] >> frecvente[i];
}
int radacina = construiesteHuffman(caractere, frecvente, n);
cout << "\nCoduri Huffman:\n";
char cod[100];
afiseazaCoduri(radacina, cod, 0);
return 0;
}4. Planificarea Joburilor cu Deadline
Maximizează profitul executând joburi înainte de deadline.
Enunț
Se dau n joburi, fiecare cu un deadline și un profit. Fiecare job necesită o unitate de timp. Maximizează profitul total respectând deadline-urile.
Exemplu
Joburi: (id, deadline, profit)
(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)
Ieșire: Profit maxim = 60 (Job 3 la t=1, Job 1 la t=4)
#include <iostream>
using namespace std;
struct Job {
int id;
int deadline;
int profit;
};
// Sortare descrescatoare dupa profit
void sorteazaDupaProfit(Job jobs[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (jobs[j].profit < jobs[j + 1].profit) {
Job temp = jobs[j];
jobs[j] = jobs[j + 1];
jobs[j + 1] = temp;
}
}
}
}
int planificareJoburi(Job jobs[], int n, int rezultat[], int& numarJoburi) {
sorteazaDupaProfit(jobs, n);
// Gaseste deadline-ul maxim
int maxDeadline = 0;
for (int i = 0; i < n; i++) {
if (jobs[i].deadline > maxDeadline) {
maxDeadline = jobs[i].deadline;
}
}
// Slot-uri de timp (-1 = liber)
int slot[100];
for (int i = 0; i <= maxDeadline; i++) {
slot[i] = -1;
}
int profitTotal = 0;
numarJoburi = 0;
for (int i = 0; i < n; i++) {
// Cauta un slot liber de la deadline in jos
for (int j = jobs[i].deadline; j >= 1; j--) {
if (slot[j] == -1) {
slot[j] = i;
rezultat[numarJoburi] = jobs[i].id;
profitTotal += jobs[i].profit;
numarJoburi++;
break;
}
}
}
return profitTotal;
}
int main() {
int n;
cout << "Numarul de joburi: ";
cin >> n;
Job jobs[100];
int rezultat[100];
cout << "Introduceti deadline si profit pentru fiecare job:\n";
for (int i = 0; i < n; i++) {
jobs[i].id = i + 1;
cin >> jobs[i].deadline >> jobs[i].profit;
}
int numarJoburi;
int profit = planificareJoburi(jobs, n, rezultat, numarJoburi);
cout << "\nJoburi planificate: ";
for (int i = 0; i < numarJoburi; i++) {
cout << rezultat[i] << " ";
}
cout << "\nProfit total: " << profit << endl;
return 0;
}5. Problema Restului (Monede)
Găsește numărul minim de monede pentru a forma o sumă.
Enunț
Se dă un set de monede cu valori diferite și o sumă S. Găsește numărul minim de monede necesare pentru a forma suma. (Funcționează optim pentru sisteme canonice de monede)
Exemplu
Monede: [1, 5, 10, 25, 50]
Suma: 93
Ieșire: 50 + 25 + 10 + 5 + 1 + 1 + 1 = 7 monede
#include <iostream>
using namespace std;
// Sortare descrescatoare
void sorteazaDesc(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] < arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int numarMinimMonede(int monede[], int n, int suma, int folosite[]) {
sorteazaDesc(monede, n);
int totalMonede = 0;
int sumaRamasa = suma;
cout << "\nDescompunere:\n";
for (int i = 0; i < n && sumaRamasa > 0; i++) {
// Cate monede de acest tip putem folosi?
folosite[i] = sumaRamasa / monede[i];
if (folosite[i] > 0) {
cout << monede[i] << " x " << folosite[i] << " = "
<< (monede[i] * folosite[i]) << endl;
sumaRamasa -= monede[i] * folosite[i];
totalMonede += folosite[i];
}
}
if (sumaRamasa > 0) {
cout << "Nu se poate forma suma exact cu monedele date!\n";
return -1;
}
return totalMonede;
}
int main() {
int n, suma;
cout << "Numarul de tipuri de monede: ";
cin >> n;
int monede[100], folosite[100];
cout << "Valorile monedelor: ";
for (int i = 0; i < n; i++) {
cin >> monede[i];
folosite[i] = 0;
}
cout << "Suma de format: ";
cin >> suma;
int rezultat = numarMinimMonede(monede, n, suma, folosite);
if (rezultat != -1) {
cout << "\nNumar minim de monede: " << rezultat << endl;
}
return 0;
}6. Arbore Parțial de Cost Minim (Prim)
Conectează toate nodurile cu cost minim.
Enunț
Se dă un graf neorientat ponderat. Găsește submulțimea de muchii care conectează toate nodurile cu costul total minim (arbore parțial de cost minim).
#include <iostream>
using namespace std;
const int MAXN = 100;
const int INF = 999999;
int graf[MAXN][MAXN]; // matrice de adiacenta cu costuri
int n, m; // noduri, muchii
void prim() {
int cheie[MAXN]; // cost minim pentru a ajunge la nod
int parinte[MAXN]; // parintele in MST
bool inMST[MAXN]; // inclus in MST?
// Initializare
for (int i = 0; i < n; i++) {
cheie[i] = INF;
inMST[i] = false;
parinte[i] = -1;
}
// Incepem de la nodul 0
cheie[0] = 0;
for (int count = 0; count < n; count++) {
// Gaseste nodul cu cheia minima care nu e in MST
int u = -1;
int minCheie = INF;
for (int v = 0; v < n; v++) {
if (!inMST[v] && cheie[v] < minCheie) {
minCheie = cheie[v];
u = v;
}
}
if (u == -1) break; // graf neconex
inMST[u] = true;
// Actualizeaza cheile vecinilor
for (int v = 0; v < n; v++) {
if (graf[u][v] != 0 && !inMST[v] && graf[u][v] < cheie[v]) {
parinte[v] = u;
cheie[v] = graf[u][v];
}
}
}
// Afiseaza MST
cout << "\nMuchiile din Arborele Partial de Cost Minim:\n";
int costTotal = 0;
for (int i = 1; i < n; i++) {
if (parinte[i] != -1) {
cout << parinte[i] + 1 << " -- " << i + 1
<< " (cost: " << graf[parinte[i]][i] << ")\n";
costTotal += graf[parinte[i]][i];
}
}
cout << "\nCost total MST: " << costTotal << endl;
}
int main() {
cout << "Numarul de noduri si muchii: ";
cin >> n >> m;
// Initializeaza graful cu 0
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graf[i][j] = 0;
}
}
cout << "Introduceti muchiile (nod1 nod2 cost):\n";
for (int i = 0; i < m; i++) {
int u, v, cost;
cin >> u >> v >> cost;
u--; v--; // 0-indexed
graf[u][v] = cost;
graf[v][u] = cost;
}
prim();
return 0;
}Complexitate și Comparații
Analiza eficienței algoritmilor greedy prezentați.
| Algoritm | Timp | Spațiu | Observații |
|---|---|---|---|
| Selecția Activităților | O(n²) | O(n) | O(n log n) cu sortare optimă |
| Rucsac Fracționar | O(n²) | O(n) | O(n log n) cu sortare optimă |
| Huffman | O(n log n) | O(n) | Cu heap implementat manual |
| Planificare Joburi | O(n²) | O(n) | Poate fi O(n log n) cu Union-Find |
| Rest Monede | O(n × suma) | O(n) | Greedy funcționează pt. sisteme canonice |
| Prim MST | O(V²) | O(V²) | O(E log V) cu heap |
Când să folosești Greedy?
✓ Potrivit pentru
Probleme cu proprietatea de alegere greedy și substructură optimală: selecție de intervale, MST, codificări, planificare.
✗ Nu funcționează pentru
Rucsac 0/1, drumuri minime cu costuri negative, probleme unde optimul local nu duce la optimul global.
Sfaturi pentru Implementare
Practici recomandate pentru rezolvarea problemelor greedy fără STL.
Sortare Manuală
Implementează algoritmi de sortare eficienți: Quick Sort pentru cazul mediu O(n log n), sau Merge Sort pentru stabilitate.
Structuri de Date
Folosește structuri (struct) pentru a grupa datele asociate și a facilita sortarea după diferite criterii.
Verifică Corectitudinea
Demonstrează matematic că strategia greedy aleasă produce soluția optimă înainte de implementare.
Identifică Criteriul
Criteriul de selecție este cheia. Încearcă diferite criterii pe exemple mici pentru a găsi pe cel corect.