Pular para o conteúdo

O que faz um algoritmo guloso funcionar

Aula 1 de 5 · 5 min

O que faz um algoritmo guloso funcionar

Passo 1 de 9

O algoritmo guloso (greedy) tem uma regra só: pegue a maior moeda que ainda cabe e nunca reconsidere.

A ideia

Um algoritmo guloso (greedy) faz a jogada que parece melhor agora e nunca volta atrás. Sem árvore de busca, sem desfazer — uma passada.

Isso só é correto quando um ganho local nunca custa uma resposta global melhor. A prova usual é um argumento de troca: pegue qualquer resposta ótima, coloque nela a escolha gulosa e mostre que o resultado continua ótimo. Se essa troca sempre se sustenta, o guloso é seguro. Basta um contraexemplo para não ser.

Exemplo do mundo real

Dar troco no caixa. Com moedas de 25, 10, 5 e 1, pegar a maior moeda que ainda cabe é sempre ótimo. Invente uma moeda com valores 1, 3 e 4 e o mesmo reflexo paga 4 + 1 + 1 por seis, quando duas de três bastariam.

O código

Sua vez

O que isto imprime?

print(greedy_coins([1, 5, 7], 10))

Mini quiz

1 / 3

O que um algoritmo guloso nunca faz?