Déanann algartam greedy an rogha logánta is fearr ar gach céim, ag súil go dtí go dtuigfidh sé go dtí uachtar domhanda. Tá sé simplí agus gasta, ach ní bhíonn sé ceart ach amháin nuair a bhíonn an airíonna roghnúcháin greedy agus struchtúir bhunochtach ar an bhfadhb.
Na roghnuithe atá caite a chíoradh arís - gealltanas don bhealach ar fheabhas is gaire agus ar aghaidh.
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]
Tá sé seo barrmhaith do bhoinn na Stáit Aontaithe, ach theipeann ar thacar ar nós {1, 3, 4} áit ar tugann greedy 4+1+1 do 6 ina áit 3+3.
Samplaí a oibríonn: Dijkstra, Kruskal/Prim (MST), códú Huffman, pleanáil eatramh.
Go hiondúil gasta — go minic O(n log n) tar éis sórtála.
Ní bhíonn greedy i gcónaí ceart. Cruthaigh an airíonna roghnúcháin greedy nó déan triail i gcoinne bhunlíne fórsabhruachta/DP sula bhraistineas fúithi.
Nuair a bhíonn greedy i bhfeidhm, tá sé i bhfad níos simplí agus níos gasta ná DP nó fórsa bruach.
Bheith ar eolas nuair a bhíonn sé bailí — agus nuair a thugann sé freagra bréagach i ngan fhios — is comhartha é de sheanadas algartamach.
Tá gráinne greedy i gcroílár go leor algartam graif bhunaidh.