Algoritmi Greedy în C++

Ce este un Algoritm Greedy?

Un algoritm care face alegerea local optimă la fiecare pas, sperând să ajungă la soluția global optimă.

Când funcționează Greedy?

1. •Proprietatea alegerii greedy: alegerea locală duce la soluție globală
2. •Substructură optimă: soluția optimă conține soluții optime ale subproblemelor

Problema Selecției Activităților

Selectează numărul maxim de activități care nu se suprapun.

Copiază
1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6struct Activitate {
7    int start, sfarsit;
8};
9
10int selectieActivitati(vector<Activitate>& activitati) {
11    // Sortăm după timpul de sfârșit
12    sort(activitati.begin(), activitati.end(),
13        [](const Activitate& a, const Activitate& b) {
14            return a.sfarsit < b.sfarsit;
15        });
16    
17    int count = 1;
18    int ultimulSfarsit = activitati[0].sfarsit;
19    
20    for (int i = 1; i < activitati.size(); i++) {
21        if (activitati[i].start >= ultimulSfarsit) {
22            count++;
23            ultimulSfarsit = activitati[i].sfarsit;
24        }
25    }
26    
27    return count;
28}

Problema Bancnotelor (Coin Change Greedy)

Copiază
1// Funcționează doar pentru anumite sisteme de bancnote (ex: 1, 5, 10, 25)
2vector<int> bancnote(int suma, vector<int>& valori) {
3    vector<int> rezultat;
4    
5    // Sortăm descrescător
6    sort(valori.rbegin(), valori.rend());
7    
8    for (int v : valori) {
9        while (suma >= v) {
10            rezultat.push_back(v);
11            suma -= v;
12        }
13    }
14    
15    return rezultat;
16}

Problema Job Scheduling

Maximizează profitul din joburi cu deadline.

Copiază
1struct Job {
2    int id, deadline, profit;
3};
4
5int jobScheduling(vector<Job>& jobs) {
6    // Sortăm după profit descrescător
7    sort(jobs.begin(), jobs.end(),
8        [](const Job& a, const Job& b) {
9            return a.profit > b.profit;
10        });
11    
12    int maxDeadline = 0;
13    for (const auto& j : jobs)
14        maxDeadline = max(maxDeadline, j.deadline);
15    
16    vector<int> slot(maxDeadline + 1, -1);
17    int profitTotal = 0;
18    
19    for (const auto& job : jobs) {
20        // Găsim cel mai târziu slot disponibil
21        for (int j = job.deadline; j > 0; j--) {
22            if (slot[j] == -1) {
23                slot[j] = job.id;
24                profitTotal += job.profit;
25                break;
26            }
27        }
28    }
29    
30    return profitTotal;
31}

Huffman Coding

Copiază
1#include <queue>
2
3struct NodHuffman {
4    char ch;
5    int frecv;
6    NodHuffman *stang, *drept;
7    
8    NodHuffman(char c, int f) : ch(c), frecv(f), stang(nullptr), drept(nullptr) {}
9};
10
11struct Compare {
12    bool operator()(NodHuffman* a, NodHuffman* b) {
13        return a->frecv > b->frecv;
14    }
15};
16
17NodHuffman* construiesteHuffman(vector<pair<char, int>>& freq) {
18    priority_queue<NodHuffman*, vector<NodHuffman*>, Compare> pq;
19    
20    for (auto& p : freq)
21        pq.push(new NodHuffman(p.first, p.second));
22    
23    while (pq.size() > 1) {
24        NodHuffman* stang = pq.top(); pq.pop();
25        NodHuffman* drept = pq.top(); pq.pop();
26        
27        NodHuffman* parinte = new NodHuffman('\0', stang->frecv + drept->frecv);
28        parinte->stang = stang;
29        parinte->drept = drept;
30        
31        pq.push(parinte);
32    }
33    
34    return pq.top();
35}

Greedy vs Programare Dinamică