Ce sunt algoritmii lacomi și când funcționează?

Question

Accepted Answer

Un **algoritm lacom** face **alegerea local optimă** la fiecare pas, sperând că duce la un optimum global. Este simplu și rapid, dar doar corect atunci când problema are **proprietatea alegerii lacomi** și **subestructura optimă**.

## Ideea

Nu reconsiderem niciodată alegerile anterioare — angajați-vă la cea mai bună opțiune imediată și mergeți mai departe.

## Exemplu: schimb de monede cu monede canonice

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

Aceasta este optimă pentru monedele americane, dar **eșuează** pentru seturi cum ar fi {1, 3, 4} unde lacom dă 4+1+1 pentru 6 în loc de 3+3.

## Când funcționează lacom

- **Subestructura optimă:** o soluție optimă conține sub-soluții optime.
- **Proprietatea alegerii lacomi:** un optimum local face parte dintr-un optimum global.

Exemple care funcționează: Dijkstra, Kruskal/Prim (MST), codificarea Huffman, planificarea intervalelor.

## Complexitate

De obicei rapid — deseori O(n log n) după sortare.

## Capcane

Lacom **nu este întotdeauna corect**. Demonstrați proprietatea alegerii lacomi sau testați împotriva unui baseline brute-force/DP înainte de a avea încredere.

## De ce este important

Când lacom se aplică, este mult mai simplu și mai rapid decât DP sau brute force.

Știind *când* este valid — și când în tăcere dă răspunsuri greșite — este o marcă a maturității algoritmice.

Multi algoritmi fundamentali de grafuri sunt lacomi în inimă.