Metoda Greedy în Programare 1
1. Obiectivele lecției:
- Să înțeleagă conceptul metodei greedy.
- Să învețe cum să identifice problemele care pot fi rezolvate folosind metoda greedy.
- Să implementeze exemple practice pentru a înțelege aplicabilitatea metodei greedy.
2. Ce este metoda Greedy?
- Definiție:
Metoda greedy (lăcomitoare) este o tehnică de rezolvare a problemelor care face alegerea optimă la fiecare pas, sperând că această strategie va conduce la soluția optimă globală. - Caracteristici principale:
- Alegerea este făcută local (la fiecare pas) pe baza unei reguli de selecție.
- Alegerea locală trebuie să fie ireversibilă.
- Este eficientă din punct de vedere al timpului pentru multe probleme.
- Cerinte pentru aplicabilitate:
- Proprietatea greedy: Alegerea locală optimă trebuie să conducă la soluția globală optimă.
- Substructură optimă: O soluție optimă pentru problemă poate fi obținută combinând soluțiile optime pentru subproblemele sale.
3. Etapele metodei Greedy
- Analiza problemei:
Identificați dacă problema îndeplinește cerințele metodei greedy. - Definirea regulii greedy:
Formulați criteriul după care se face alegerea optimă la fiecare pas. - Implementarea algoritmului:
Efectuați alegerile în mod iterativ, până când atingeți o soluție completă. - Validarea soluției:
Verificați dacă soluția obținută este corectă și optimă.
4. Avantaje și dezavantaje
| Avantaje | Dezavantaje |
| Simplu de înțeles și implementat. | Nu garantează soluția optimă pentru toate problemele. |
| Eficient din punct de vedere al timpului. | Necesită o analiză atentă pentru a verifica aplicabilitatea. |
| Util în probleme cu substructuri optime. | Greșeli în alegerea regulii pot duce la soluții greșite. |
5. Exemple practice
Exemplu 1: Problema monedelor
- Problema:
Se dorește să se determine numărul minim de monede necesar pentru a forma o sumă SSS, folosind monede de valori date. - Algoritm greedy:
- Alege moneda cu valoarea cea mai mare care este mai mică sau egală cu suma rămasă.
- Continuă până când suma devine 000.
- Implementare:
#include <iostream>
#include <vector>
using namespace std;
void problemaMonedelor(vector<int>& monede, int suma) {
sort(monede.rbegin(), monede.rend()); // Sortare descrescătoare
vector<int> utilizate;
for (int moneda : monede) {
while (suma >= moneda) {
suma -= moneda;
utilizate.push_back(moneda);
}
}
if (suma == 0) {
cout << „Monede utilizate: „;
for (int moneda : utilizate) {
cout << moneda << ” „;
}
cout << endl;
} else {
cout << „Nu se poate obține suma dorită cu monedele disponibile.” << endl;
}
}
int main() {
vector<int> monede = {1, 5, 10, 25, 50};
int suma = 87;
problemaMonedelor(monede, suma);
return 0;
}
Exemplu 2: Problema rucsacului fracționar
- Problema:
Avem un rucsac cu o capacitate maximă CCC și nnn obiecte, fiecare cu o greutate wiw_iwi și o valoare viv_ivi. Determinați valoarea maximă care poate fi transportată, permițând divizarea obiectelor. - Algoritm greedy:
- Sortează obiectele în funcție de valoarea per unitatea de greutate (viwi\frac{v_i}{w_i}wivi).
- Adaugă obiectele în rucsac în ordine descrescătoare a raportului, până când rucsacul este plin.
- Implementare:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Obiect {
int greutate;
int valoare;
double raport() const {
return (double) valoare / greutate;
}
};
bool compara(const Obiect& a, const Obiect& b) {
return a.raport() > b.raport();
}
double rucsacFractionar(vector<Obiect>& obiecte, int capacitate) {
sort(obiecte.begin(), obiecte.end(), compara);
double valoareTotala = 0.0;
for (const Obiect& obj : obiecte) {
if (capacitate >= obj.greutate) {
capacitate -= obj.greutate;
valoareTotala += obj.valoare;
} else {
valoareTotala += obj.raport() * capacitate;
break;
}
}
return valoareTotala;
}
int main() {
vector<Obiect> obiecte = {{10, 60}, {20, 100}, {30, 120}};
int capacitate = 50;
cout << „Valoarea maximă: ” << rucsacFractionar(obiecte, capacitate) << endl;
return 0;
}
Exemplu 3: Activități care nu se suprapun
- Problema:
Avem nnn activități, fiecare definită prin ore de început și sfârșit. Alegeți numărul maxim de activități care nu se suprapun. - Algoritm greedy:
- Sortează activitățile în funcție de ora de sfârșit.
- Selectează activitățile care încep după terminarea celei selectate anterior.
- Implementare:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activitate {
int inceput;
int sfarsit;
};
bool compara(const Activitate& a, const Activitate& b) {
return a.sfarsit < b.sfarsit;
}
int selecteazaActivitati(vector<Activitate>& activitati) {
sort(activitati.begin(), activitati.end(), compara);
int numarActivitati = 1;
int ultimaSfarsit = activitati[0].sfarsit;
for (size_t i = 1; i < activitati.size(); i++) {
if (activitati[i].inceput >= ultimaSfarsit) {
numarActivitati++;
ultimaSfarsit = activitati[i].sfarsit;
}
}
return numarActivitati;
}
int main() {
vector<Activitate> activitati = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
cout << „Numărul maxim de activități: ” << selecteazaActivitati(activitati) << endl;
return 0;
}
6. Activități practice pentru elevi
- Implementați metoda greedy pentru a rezolva problema împărțirii unui număr întreg NNN în cât mai puține pătrate perfecte (ex.: 12=4+4+412 = 4 + 4 + 412=4+4+4).
- Scrieți un program care determină numărul minim de intervale care acoperă un set de puncte date.
- Creați un algoritm greedy pentru a găsi traseul minim într-o matrice de costuri, pornind din colțul stânga-sus și terminând în colțul dreapta-jos.
7. Concluzie
- Metoda greedy este o abordare simplă și eficientă pentru rezolvarea problemelor care îndeplinesc cerințele de substructură optimă și proprietatea greedy.
- Alegerea regulii greedy este crucială pentru obținerea soluției optime.
- Practica și analiza problemelor ajută la identificarea situațiilor în care metoda greedy este aplicabilă.