Troco em moedas: método guloso contra solução ótima

Introduza um conjunto de moedas e um valor. A página compõe esse valor de duas formas: pelo método guloso, escolhendo sempre a maior moeda que serve até já não restar nada ou não haver nenhuma moeda adequada; e com o menor número possível de moedas, preenchendo uma tabela de 0 até ao valor indicado. Abaixo da tabela aparecem todos os valores até ao limite que escolher, com os casos em que o método guloso usa mais moedas do que o necessário devidamente assinalados.

Exemplo resolvido — Troco em moedas: método guloso contra solução ótima

Método guloso, começando pela maior moeda	3 moedas
Menor número de moedas, segundo a tabela	2 moedas: 2×24
Moedas que o método guloso desperdiça aqui	1
Quantias de 1 a 240 em que o método guloso perde	42 de 240
Maior desperdício do método guloso entre 1 e 240	1
Menor quantia em que o método guloso perde	48

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Troco em moedas: método guloso contra solução ótima

O problema do troco consiste em encontrar o menor número de moedas que perfaz uma dada quantia, partindo de um conjunto de denominações e admitindo qualquer quantidade de cada uma. O algoritmo guloso escolhe repetidamente a maior moeda que não excede o valor em falta. A programação dinâmica resolve o problema de forma exata, calculando primeiro todas as quantias menores: M(0) = 0 e M(a) = 1 + min M(a − c) para as moedas c ≤ a. Um sistema de moedas em que o método guloso é ótimo para todas as quantias chama-se canónico.

O que significa cada símbolo

M(a): o menor número de moedas que perfaz a quantia a; é o número na célula a da tabela
G(a): o número de moedas que o método guloso usa para a
cₘ, cₘ₋₁: a maior e a segunda maior moeda; se existir uma primeira quantia em que o método guloso perde, ela é inferior à soma de ambas

Pressupõe: Pressupõe-se uma quantidade ilimitada de cada moeda, denominações inteiras e o número de moedas como único custo. Uma caixa registadora sem florins coloca outro problema. O limite exige uma moeda de 1; sem ela, algumas quantias são impossíveis de pagar e o método guloso pode ficar aquém de uma quantia que a tabela consegue pagar.

O antigo dinheiro britânico venceu o método guloso nos quatro xelins 🖖

Prima RU antes de 1971. Para pagar 48d, quatro xelins, o método guloso escolhe a maior moeda possível: uma meia-coroa (30d), seguida de um xelim (12d) e de seis pence (6d), três moedas. Dois florins de 24d perfazem os mesmos 48d com apenas duas. A partir daí, o método perde em seis quantias por cada trinta pence: 48–53d, 78–83d e assim sucessivamente até 228–233d. São 42 das 240 quantias de uma libra. Em cada caso, desperdiça exatamente uma moeda; por isso, todas as barras vermelhas da faixa têm a mesma altura. Essas seis quantias deixam entre 18 e 23 pence depois de uma ou mais meias-coroas. Se se devolver uma meia-coroa e se pagarem 48d com dois florins, poupa-se uma moeda. O meio penny não resolve o problema. Introduza as moedas em meios pence, 1, 2, 6, 12, 24, 48, 60, e verifique até 480. A primeira falha surge nos 96 meios pence, ainda 48d; o método guloso perde em 84 das 480 quantias, as mesmas 42 e o meio penny imediatamente acima de cada uma.

Sem a meia-coroa, o método guloso nunca falha 🖖

Prima Sem meia-coroa. Ficam as mesmas moedas menos uma, 1, 3, 6, 12 e 24 pence, e a faixa fica vazia: o método guloso não perde em nenhuma das 240 quantias. Cada moeda divide a seguinte. Numa cadeia assim, o método não pode perder, pois qualquer conjunto de moedas que valha a moeda imediatamente superior pode ser trocado por essa única moeda. A meia-coroa quebra a cadeia. Trinta não é múltiplo de vinte e quatro, e dois florins equivalem a uma meia-coroa mais 18d, que exigem um xelim e seis pence; todas as falhas da primeira faixa resultam dessa troca. Acrescentar uma moeda também não resolve o problema. Introduza 1, 3, 6, 12, 24, 30, 60 para repor a coroa, no valor de cinco xelins: a contagem desce de 42 para 24, mas 48d continua a ser a primeira falha, porque uma coroa não ajuda a pagar quantias inferiores ao seu próprio valor.

Verificar um sistema de moedas é uma tarefa finita 🖖

Uma falha do método guloso em 48d ainda nada diz sobre 4 800d. Um teorema de Dexter Kozen e Shmuel Zaks, publicado em 1994, permite decidir um sistema para todas as quantias: se houver uma moeda de 1 e o método guloso perder em algum caso, a menor quantia em que isso acontece fica estritamente entre c₃ + 1 e c_m + c_m−1. Aqui, c₃ é a terceira menor moeda; c_m e c_m−1 são as duas maiores. Prima Cêntimos dos EUA. As duas maiores moedas são 100 e 50. Nada falha abaixo de 150, e essa verificação finita abrange todas as quantias possíveis; no euro, chega a 300. O limite não pode ser estreitado. Prima 1, 3, 4: a janela entre 5 e 7 contém uma única quantia, 6, precisamente aquela em que o método guloso perde. A linha tracejada da faixa representa o limite. Quando existe uma moeda de 1, a primeira barra vermelha fica sempre à sua esquerda.

Problema resolvido na íntegra

Que terceira moeda se pode juntar a 1 e 5? 3 passos
Um país tem moedas de 1 e 5 e pretende criar uma terceira, d, com valor entre 6 e 30. Para que valores de d será sempre ótimo o método guloso? A página testa um sistema de cada vez, mas a regra de Kozen e Zaks para três moedas decide os 25 casos de uma só vez. Prima 1, 3, 4 para experimentar primeiro a regra num sistema já testado pela página.

Abrir este problema na ferramenta
1. Para moedas 1 < c < d, a regra é esta: escreva d = qc + r, com 0 ≤ r < c. O sistema falha em algum caso se e somente se 0 < r < c − q. Para 1, 3, 4, temos d = 4 = 1 × 3 + 1, logo q = 1 e r = 1; verifica-se 0 < 1 < 2. O sistema falha, e a página encontra a primeira falha em 6:
  
  $4 = 1 \times 3 + 1 : q = 1, r = 1, 0 < 1 < 3 - 1 = 2$
2. Agora c = 5, portanto d = 5q + r e o teste é 0 < r < 5 − q. Quanto maior for q, menos valores possíveis restam para r:
  
  $d = 5 q + r, 0 \leq r < 5 : 0 < r < 5 - q$
3. Para q = 1 (d de 6 a 9), r pode ser 1, 2 ou 3, pelo que d = 6, 7 e 8 falham. Para q = 2 (10 a 14), r = 1 ou 2: falham 11 e 12. Para q = 3 (15 a 19), só r = 1: falha 16. A partir de q = 4, 5 − q é 1 ou menos e nenhum valor de r satisfaz a condição:
  
  $q = 1 : d \in {6, 7, 8} q = 2 : d \in {11, 12} q = 3 : d = 16 q \geq 4 : 5 - q \leq 1$
Resposta

Falham seis valores: 6, 7, 8, 11, 12 e 16. Os outros dezanove funcionam, incluindo todos os valores de d entre 17 e 30. Introduza 1, 5, 12 para observar um dos seis casos: o método guloso paga 15 com 12 + 1 + 1 + 1, quatro moedas, quando bastam três moedas de cinco.

$d \in {6, 7, 8, 11, 12, 16} 15 = 12 + 1 + 1 + 1 = 5 + 5 + 5$

Percurso de aprendizagem

Por que razão um algoritmo está correto

Referências (3)

The bound the page draws as a dashed line and settles every system with: if greedy is ever beaten, the smallest amount where it is beaten lies strictly between c₃ + 1 and cₘ + cₘ₋₁; the three-coin rule the worked problem uses; the {1, 3, 4} example and the US system 1, 5, 10, 25, 50, 100 as canonical: D. Kozen and S. Zaks, "Optimal bounds for the change-making problem." Theoretical Computer Science 123(2), 1994, pp. 377-388. DOI 10.1016/0304-3975(94)90134-1
The pre-decimal coins and their values in pence (threepence, sixpence, shilling of 12d, florin of two shillings, half-crown of two shillings and sixpence, crown of five shillings), and the halfpenny's end as legal tender on 31 July 1969: Wikipedia contributors, "£sd", Wikipedia, The Free Encyclopedia, accessed 3 October 2026.
Which coins made up the circulating set at the end, as the Royal Mint itself issued them in 1970: half-crown, florin, shilling, sixpence, threepence, penny and halfpenny: The Royal Mint, "1970 Pre-Decimal UK Proof Set", product description, accessed 3 October 2026.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.