Što su pohlepni algoritmi i kada funkcioniraju?

Question

Accepted Answer

**Pohlepni algoritam** čini **lokalno optimalnu izboru** u svakom koraku, nadajući se da vodi do globalnog optimuma. Jednostavan je i brz, ali je ispravan samo kada problem ima **svojstvo pohlepnog izbora** i **optimalnu podstrukturu**.

## Ideja

Nikad ne razmatraj prošle izbore — obavežite se na najbolju trenutnu opciju i kreni dalje.

## Primjer: izmjena novčića s kanoničkim kovanicama

```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]
```

Ovo je optimalno za američki novčić, ali **ne funkcionira** za skupove kao što je {1, 3, 4} gdje pohlepan daje 4+1+1 za 6 umjesto 3+3.

## Kada pohlepan funkcionira

- **Optimalna podstruktura:** optimalno rješenje sadrži optimalna pod-rješenja.
- **Svojstvo pohlepnog izbora:** lokalni optimum je dio globalnog optimuma.

Primjeri koji funkcioniraju: Dijkstra, Kruskal/Prim (MST), Huffman kodiranje, planiranje intervala.

## Složenost

Obično brz — često O(n log n) nakon sortiranja.

## Zamke

Pohlepan **nije uvijek ispravan**. Dokaži svojstvo pohlepnog izbora ili testiraj naspram brute-force/DP baseline prije nego što mu vjeruješ.

## Zašto je to važno

Kada se pohlepan primijeni, on je daleko jednostavniji i brži od DP ili brute forcea.

Znati *kada* je validan — i kada šutljivo daje pogrešne odgovore — znak je algoritmske zrelosti.

Mnogi temeljni algoritmi grafova su pohlepni po srcu.