Un algoritmo greedy è un algoritmo che ad ogni passaggio sceglie la variante ottimale (all'interno del passaggio corrente) nell'aspettativa che la soluzione finale sia ottimale in senso globale.
Piccolo esempio:
Supponiamo di avere un numero illimitato di monete di tagli diversi e di dover prelevare l'importo S. Consideriamo due casi specifici, ciascuno dei quali cercheremo di risolvere con un algoritmo goloso.
Vale a dire, agiremo come segue: ad ogni passaggio prenderemo una moneta del taglio più alto (l'opzione migliore all'interno del passaggio), che non superi l'importo rimanente.
a) Siano i tagli delle monete 1, 5 e 10, e S = 27.
1) Prendi 10, S: 27 -> 17
2) Prendi 10, S: 17 -> 7
3) Prendi 5, S: 7 -> 2
4) Prendi 1, S: 2 -> 1
5) Prendi 1, S: 1 -> 0
Di conseguenza, hanno segnato la quantità di cinque monete. Puoi indipendentemente (ad esempio, forza bruta) assicurarti che per 4 monete o meno non sarai in grado di segnare 27.
b) Siano i tagli delle monete 1, 5 e 7, e S = 24.
1) Prendi 7, S: 24 -> 17
2) Prendi 7, S: 17 -> 10
3) Prendi 7, S: 10 -> 3
4) Prendi 1, S: 3 -> 2
5) Prendi 1, S: 2 -> 1
6) Prendi 1, S: 1 -> 0.
Abbiamo ottenuto un punteggio con sei monete, ma potremmo ottenere un punteggio S con quattro monete: due con un valore nominale di 7 e due con un valore nominale di 5.
Come si può vedere dall'esempio, non è sempre possibile risolvere problemi con un algoritmo greedy. Ma se porta a una risposta ottimale complessiva, di solito sarà più facile che usare la programmazione dinamica o altri metodi.