Algoritm Greedy C++ — Ghid Complet cu Exemple

Ce este Tehnica Greedy?

Greedy (lacom) este o strategie algoritmică ce construiește soluția pas cu pas, alegând la fiecare pas cea mai bună opțiune locală, sperând că va duce la un optim global.

Când funcționează Greedy?

• •Problema are substructură optimă
• •Alegerea greedy locală nu compromite soluția globală

Probleme Clasice Greedy

1. Problema Selecției Activităților

Copiază
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Activitate { int start, finish; };
5
6int maxActivitati(vector<Activitate>& act) {
7    sort(act.begin(), act.end(), [](auto& a, auto& b){
8        return a.finish < b.finish;  // sortare după timp de finalizare
9    });
10    
11    int count = 1, lastFinish = act[0].finish;
12    for (int i = 1; i < act.size(); i++) {
13        if (act[i].start >= lastFinish) {
14            count++;
15            lastFinish = act[i].finish;
16        }
17    }
18    return count;
19}

2. Problema Restului (Coin Change Greedy)

Copiază
1void rest(int suma, vector<int>& monede) {
2    sort(monede.rbegin(), monede.rend());  // descrescător
3    for (int m : monede) {
4        while (suma >= m) {
5            cout << m << " ";
6            suma -= m;
7        }
8    }
9}
10// Atenție: funcționează doar pentru sisteme monetare canonice!

3. Algoritmul lui Kruskal — Arbore Parțial de Cost Minim

Copiază
1struct Muchie { int u, v, cost; };
2int parent[1001], rang[1001];
3
4int find(int x) {
5    if (parent[x] != x) parent[x] = find(parent[x]);
6    return parent[x];
7}
8
9void unite(int x, int y) {
10    int rx = find(x), ry = find(y);
11    if (rang[rx] < rang[ry]) swap(rx, ry);
12    parent[ry] = rx;
13    if (rang[rx] == rang[ry]) rang[rx]++;
14}
15
16int kruskal(int n, vector<Muchie>& muchii) {
17    sort(muchii.begin(), muchii.end(), [](auto& a, auto& b){ return a.cost < b.cost; });
18    for (int i = 1; i <= n; i++) { parent[i] = i; rang[i] = 0; }
19    
20    int costTotal = 0;
21    for (auto& m : muchii) {
22        if (find(m.u) != find(m.v)) {
23            unite(m.u, m.v);
24            costTotal += m.cost;
25        }
26    }
27    return costTotal;
28}

4. Problema Rucsacului Fracționar

Copiază
1struct Item { double greutate, valoare; };
2
3double rucsacFractionar(vector<Item>& items, double capacitate) {
4    sort(items.begin(), items.end(), [](auto& a, auto& b){
5        return a.valoare/a.greutate > b.valoare/b.greutate;  // raport val/gr descrescător
6    });
7    
8    double totalVal = 0;
9    for (auto& item : items) {
10        if (capacitate >= item.greutate) {
11            totalVal += item.valoare;
12            capacitate -= item.greutate;
13        } else {
14            totalVal += item.valoare * (capacitate / item.greutate);
15            break;
16        }
17    }
18    return totalVal;
19}

Greedy vs Programare Dinamică

Probleme Frecvente la BAC Informatică — Greedy

1. •Sortare greedily — ordonarea obiectelor pentru maximizare/minimizare
2. •Intervaluri — acoperire minimă, selecție maximă
3. •Codificare Huffman — compresie optimă