Algoritmo Guloso (Greedy Algorithm)

Definição

Um algoritmo guloso (greedy algorithm) é uma estratégia de solução de problemas que toma a melhor decisão local em cada etapa, com a expectativa de que isso leve à melhor solução global.

Ou seja, ele sempre escolhe a opção que parece a melhor naquele momento — sem voltar atrás ou explorar todas as possibilidades.

Por que usar

Muito eficiente para certos problemas de otimização;
Simples de implementar e fácil de entender;
Pode produzir soluções ótimas — ou boas o suficiente — em muitos casos práticos

Quando funciona bem

Algoritmos gulosos funcionam corretamente quando o problema possui a propriedade da subestrutura ótima, ou seja, a melhor solução global pode ser construída a partir das melhores escolhas locais.

Exemplos clássicos onde funciona:

Troco com moedas (se as moedas forem bem definidas);
Algoritmo de Kruskal para árvore geradora mínima;
Problema da mochila fracionária.

Complexidade

Depende do problema, mas algoritmos gulosos geralmente são muito rápidos:

Tempo típico: O(n log n) ou O(n)
Espaço adicional: varia conforme a estrutura usada

Exemplo prático (Python) — Troco com menor número de moedas

Suponha que queremos dar um troco de 87 centavos utilizando o menor número possível de moedas. As moedas disponíveis são: 100, 50, 25, 10, 5 e 1 centavo. O algoritmo a seguir usa uma abordagem gulosa para selecionar sempre a maior moeda que ainda cabe no valor restante.

def troco_guloso(valor, moedas):
    resultado = []
    moedas.sort(reverse=True)  # Começamos pelas maiores moedas possíveis

    for moeda in moedas:
        while valor >= moeda:
            valor -= moeda
            resultado.append(moeda)

    return resultado

# Exemplo
moedas = [100, 50, 25, 10, 5, 1]  # em centavos
valor = 87
print(troco_guloso(valor, moedas))  # [50, 25, 10, 1, 1]

Observação

Esse algoritmo funciona bem com moedas “padronizadas” como as do exemplo.
Em alguns sistemas monetários, a abordagem gulosa pode não dar o menor número de moedas, e seria necessário usar programação dinâmica.