Un algoritmo greedy fa la scelta localmente ottimale ad ogni passo, sperando che porti a un ottimo globale. È semplice e veloce, ma corretto solo quando il problema ha la greedy-choice property e la optimal substructure.
Non riconsiderare mai le scelte passate — impegnati per l'opzione migliore immediata e vai avanti.
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]
Questo è ottimale per le monete statunitensi, ma fallisce per insiemi come {1, 3, 4} dove greedy dà 4+1+1 per 6 invece di 3+3.
Esempi che funzionano: Dijkstra, Kruskal/Prim (MST), Huffman coding, interval scheduling.
Generalmente veloce — spesso O(n log n) dopo l'ordinamento.
Greedy non è sempre corretto. Prova la greedy-choice property o testa contro un baseline brute-force/DP prima di fidarti.
Quando greedy si applica, è molto più semplice e veloce di DP o brute force.
Sapere quando è valido — e quando silenziosamente dà risposte sbagliate — è un segno di maturità algoritmica.
Molti algoritmi grafici fondamentali sono greedy al cuore.