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.
Nikad ne razmatraj prošle izbore — obavežite se na najbolju trenutnu opciju i kreni dalje.
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.
Primjeri koji funkcioniraju: Dijkstra, Kruskal/Prim (MST), Huffman kodiranje, planiranje intervala.
Obično brz — često O(n log n) nakon sortiranja.
Pohlepan nije uvijek ispravan. Dokaži svojstvo pohlepnog izbora ili testiraj naspram brute-force/DP baseline prije nego što mu vjeruješ.
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.
Knjižnica IT pitanja za razgovore za posao s detaljnim odgovorima — od Juniora do Seniora.
Doniraj