Greedy

Consideram urmatorul scenariu: esti cu prietenii si ati pus bani sa luati de baut. Va ajunge de o sticla de whiskey. Evident, o luati pe aia, desi probabil v-ati simti mai bine pentru mai mult timp cu o lada de bere si ceva chipsuri :P

Cam asta e treaba si cu algoritmul Greedy. El ofera solutia care, la pasul curent, pare cea mai buna, fara a se gandi la viitor (pasii urmatori). Pentru anumite categorii de probleme, ne ofera solutia optima intr-un timp foarte bun, pentru altele insa ne ofera o solutie mai putin optima.

Exemplul tipic este problema rucsacului. Avem un rucsac in care putem duce cel mult o masa mmax. Avem o serie de obiecte avand o masa masa[i] si o valoare val[i]. Pentru a lua doar obiectele cele mai importante, facem un raport valoare/masa, il sortam si luam pe rand obiectele cu raportul maxim.

Sunt doua tipuri de probleme: cea continua si cea discreta. La cea continua, putem lua si fragmente. Adica daca un obiect are masa 5kg, putem lua doar 2kg din obiectul respectiv. Asta merge cu greedy. Daca avem problema discreta, aka putem lua doar obiecte intregi, asta NU merge.

Sa vedem deci care e ideea de algoritm:

1. sortam obiectele dupa raportul val/masa - O (n log n)
2. parcurgem vectorul si cat timp nu s-a ajuns la o masa >mmax, mai adaugam un obiect (sau o parte dintr-un obiect) - O (n).

Complexitate: O(n log n).

Aveti aici o implementare mai simpla de greedy, care calculeaza la fiecare pas minimul dintre valorile ramase (complexitate O(n^2)) pentru a va face o idee generala cam cum merge.