Algoritmii lacomi sunt un tip de strategie algoritmică care face alegerea optimă la fiecare pas cu speranța de a găsi optimul global. Ei sunt utilizați pe scară largă în rezolvarea problemelor de optimizare în cazul în care deciziile locale conduc la o soluție optimă la nivel global. Acest articol explorează conceptul de algoritmi lacomi, oferă exemple practice, și demonstrează modul de a efectua calcule conexe.

Ce sunt algoritmile lacome?

Un algoritm lacom construiește o soluție bucată cu bucată, întotdeauna alegerea piesei următoare care oferă cel mai imediat beneficiu. Această abordare este simplă și eficientă, dar nu garantează întotdeauna cea mai bună soluție generală pentru toate problemele. Este cel mai eficient atunci când problema prezintă proprietatea lacom-alegere și substructura optimă.

Exemple practice

Problemele comune rezolvate prin utilizarea algoritmilor lacomi includ problema schimbării monedei, selectarea activității și problema fracțională a rucsacului. Aceste exemple demonstrează cum alegerea optimă la nivel local poate duce la o soluție optimă la nivel global în scenarii specifice.

Calcule și implementare

Să luăm în considerare problema schimbării monedei, în cazul în care obiectivul este de a face o schimbare pentru o anumită sumă folosind cele mai puține monede. Să presupunem că denominațiile monedei sunt 1, 5, 10 și 25 de cenți, iar valoarea țintă este de 63 de cenți. Abordarea lacomă implică selectarea celei mai mari monede mai mici sau egale cu suma rămasă la fiecare pas.

Calculul pas cu pas:

  • Alege 25 cenți (mai rămâne: 63 - 25 = 38)
  • Alege 25 cenți (mai rămâne: 38 - 25 = 13)
  • Alege 10 cenți (mai rămâne: 13 - 10 = 3)
  • Alege 1 cent (rămâne: 3 - 1 = 2)
  • Alege 1 cent (rămâne: 2 - 1 = 1)
  • Alege 1 cent (rămâne: 1 - 1 = 0)

Total monede utilizate: 6.