Um algoritmo guloso é um algoritmo que a cada passo escolhe a variante ótima (dentro do passo atual) na expectativa de que a solução final seja ótima no sentido global.
Pequeno exemplo:
Suponha que temos um número ilimitado de moedas de diferentes denominações e precisamos coletar a quantia S. Vamos considerar dois casos específicos, cada um dos quais tentaremos resolver com um algoritmo guloso.
Ou seja, agiremos da seguinte forma: em cada etapa levaremos uma moeda de maior valor (a melhor opção dentro da etapa), que não exceda o valor restante.
a) Sejam as denominações das moedas 1, 5 e 10, e S = 27.
1) Take 10, S: 27 -> 17
2) Take 10, S: 17 -> 7
3) Take 5, S: 7 -> 2
4) Take 1, S: 2 -> 1
5) Take 1, S: 1 -> 0
Como resultado, eles marcaram a quantia de cinco moedas. Você pode independentemente (por exemplo, força bruta) garantir que, com 4 moedas ou menos, não consiga marcar 27.
b) Sejam as denominações das moedas 1, 5 e 7, e S = 24.
1) Take 7, S: 24 -> 17
2) Take 7, S: 17 -> 10
3) Take 7, S: 10 -> 3
4) Take 1, S: 3 -> 2
5) Take 1, S: 2 -> 1
6) Take 1, S: 1 -> 0.
Marcamos com seis moedas, mas conseguimos marcar S com quatro moedas - duas com valor nominal de 7 e duas com valor nominal de 5.
Como pode ser visto no exemplo, nem sempre é possível resolver problemas com um algoritmo guloso. Mas se levar a uma resposta ótima geral, geralmente será mais fácil do que usar programação dinâmica ou outros métodos.