Problema do Troco
Usa a estratégia gulosa de sempre escolher a maior moeda possível — simples, eficiente e ideal para sistemas monetários padrão.
O(n)O(1)Como Funciona
Passo a passo do algoritmo
Estratégia gulosa
A ideia central é sempre fazer a escolha localmente ótima: pegar a maior moeda que caiba no valor restante. Não voltamos atrás nem reconsideramos escolhas anteriores. Para sistemas monetários convencionais, essa estratégia siempre produz o resultado globalmente ótimo.
escolher sempre a maior moeda ≤ remainingOrdenar denominações
Começamos ordenando as denominações das moedas do maior para o menor valor. Essa ordenação é feita apenas uma vez. No loop principal, sempre tentamos a maior denominação disponível primeiro.
moedas = [100, 50, 25, 10, 5, 1] // decrescenteEscolha e subtração
Para cada iteração, percorremos as moedas em ordem decrescente. Ao encontrar a primeira que cabe (moeda ≤ remaining), a adicionamos à solução e subtraímos do valor restante. Depois recomeçamos do maior valor.
para cada moeda (maior→menor):
se moeda ≤ remaining:
selected.add(moeda); remaining -= moeda; breakRepetição até zerar
O processo continua enquanto remaining > 0. A cada iteração escolhemos uma moeda. Como sempre existe a moeda de 1 centavo, o algoritmo sempre termina — em no máximo `amount` iterações.
enquanto remaining > 0: escolher próxima moedaLimitação do guloso
Para moedas fora do padrão, o guloso pode falhar. Ex: denominações [1, 3, 4], troco 6. Guloso: 4+1+1=3 moedas. Ótimo: 3+3=2 moedas. Nesses casos, use programação dinâmica (problema do troco DP).
[1,3,4] → troco 6: guloso=3 moedas, DP=2 moedasImplementação
Código comentado em JavaScript e Python
function troco(valor, moedas) {
// Ordenar moedas em ordem decrescente
const denominacoes = [...moedas].sort((a, b) => b - a);
const escolhidas = [];
let restante = valor;
while (restante > 0) {
// Encontrar a maior moeda que cabe
const moeda = denominacoes.find(m => m <= restante);
if (moeda === undefined) {
throw new Error('Troco impossível com as denominações fornecidas');
}
escolhidas.push(moeda);
restante -= moeda;
}
return escolhidas;
}
// Exemplo padrão (centavos)
const moedas = [100, 50, 25, 10, 5, 1];
const resultado = troco(87, moedas);
console.log('Moedas:', resultado);
// [25, 25, 25, 10, 1, 1] → 6 moedas
// Contar por denominação
const contagem = resultado.reduce((acc, m) => {
acc[m] = (acc[m] || 0) + 1;
return acc;
}, {});
console.log(contagem); // { 25: 3, 10: 1, 1: 2 }Playground
Visualize o algoritmo em ação
Quando Usar
Cenários ideais para este algoritmo
Sistemas de pagamento
Caixas automáticos, máquinas de venda e sistemas de ponto de venda usam estratégia gulosa para dar troco com o menor número de cédulas e moedas.
Particionamento guloso
O mesmo padrão se aplica a dividir tarefas em intervalos de tempo, alocar bandwidth, ou cobrir um intervalo com o menor número de segmentos.
Introdução a algoritmos gulosos
O problema do troco é o exemplo pedagógico clássico para ensinar o paradigma guloso e quando ele funciona (ou não).
Análise de sistemas monetários
Estudar quais conjuntos de denominações admitem solução gulosa ótima é um problema de teoria dos números com aplicações práticas em design de moedas.
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Caso geral | O(V/mᵢₙ × n) |
| Melhor caso | O(n) |
| Espaço auxiliar | O(k) |