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