Informatică Algoritmi
Probleme algoritmi greedy bacalaureat
Problemele cu algoritmi greedy la bacalaureat cer să alegi la fiecare pas cea mai bună opțiune locală, sperând să obții soluția optimă globală. Aceste probleme testează capacitatea de a identifica proprietățile de optimalitate locală și de a construi soluții incremental. Exemple frecvente includ problema rucsacului fracționar sau a planificării activităților.
Probleme tipice de bac
- Problema rucsacului fracționar Selectezi obiecte în ordinea descrescătoare a raportului valoare/greutate. Exemplu: pentru obiecte cu greutăți [10, 20, 30] și valori [60, 100, 120], rapoartele sunt 6, 5, 4; alegi întâi obiectul cu raportul 6.
- Planificarea activităților Alegi activități care nu se suprapun, sortate după ora de final. Dacă ai activități cu intervalele (1,3), (2,4), (3,5), alegi (1,3) și (3,5) pentru maxim 2 activități.
- Problema monedelor Pentru a plăti o sumă cu monede de valori date, alegi mereu cea mai mare monedă posibilă. Exemplu: pentru sumă 45 și monede [1,5,10,25], soluția greedy este 25+10+10.
Pași pentru rezolvare
- 1 Identifică proprietatea greedy Verifică dacă alegerea optimă locală duce la soluție globală; de exemplu, în problema rucsacului, raportul valoare/greutate asigură profit maxim.
- 2 Sortează datele de intrare Aranjează elementele după criteriul greedy, cum ar fi sortarea descrescătoare a rapoartelor pentru rucsac.
- 3 Construiește soluția pas cu pas Parcurge lista sortată și adaugă elemente care respectă constrângerile, cum ar fi capacitatea rucsacului sau non-suprapunerea intervalelor.
Exersează pe probleme standard pentru a recunoaște rapid tiparele greedy.