O problema do troco

Um caixa a dar o troco pega na maior moeda que cabe, depois na seguinte, e com euros ou dólares isso dá sempre o mínimo de moedas. Mas se as moedas forem 1, 3 e 4, o mesmo hábito paga 6 com três moedas quando bastariam duas. A programação dinâmica encontra o verdadeiro mínimo para quaisquer moedas.

Uma fila de montantes, cada um com o mínimo de moedas que o formam, por cima de moedas de três tamanhos diferentes
Uma fila de montantes, cada um com o mínimo de moedas que o formam, por cima de moedas de três tamanhos diferentes

Duas perguntas

O problema do troco tem duas variantes. A primeira pede o mínimo de moedas que formam um montante exato; é também conhecida como problema de dar o troco. A segunda pergunta quantas combinações diferentes de moedas o formam. Em ambas, cada tipo de moeda pode ser usado as vezes que se quiser, e ambas se resolvem construindo a resposta para cada montante a partir das respostas para montantes mais pequenos.

Mínimo de moedas, passo a passo

Faça uma fila de células para os montantes de 0 até ao alvo. O montante 0 precisa de 0 moedas; todos os outros começam em infinito. Percorra os montantes por ordem e, para cada um, experimente cada moeda c que caiba: a célula do montante menos c, mais uma moeda, é um candidato. Fique com o mais pequeno. Cada célula depende apenas de células à sua esquerda, que já são definitivas, por isso uma só passagem enche a fila.

Um exemplo

Com as moedas 1, 3 e 4: o montante 1 precisa de 1 moeda, 2 precisa de 2, 3 precisa de 1 (uma só moeda de 3) e 4 precisa de 1. Para 5, experimenta-se 1 (4 precisa de 1, logo 2 moedas), 3 (2 precisa de 2, logo 3 moedas) e 4 (1 precisa de 1, logo 2 moedas): o melhor é 2. Para 6, experimenta-se 1 (5 precisa de 2, logo 3), 3 (3 precisa de 1, logo 2) e 4 (2 precisa de 2, logo 3): o melhor é 2, com 3 + 3. O guloso teria pago 4 + 1 + 1.

Contar as maneiras

Para contar combinações, junte as moedas uma de cada vez. Só com a primeira moeda, cada montante pode ser formado de uma maneira ou de nenhuma. Quando entra uma nova moeda c, as maneiras de formar um montante a são as maneiras antigas, sem c, mais as maneiras de formar a − c com c de novo permitida, porque cada uma delas se torna uma maneira de formar a ao juntar mais uma moeda c. Com as moedas 1, 2 e 5 há 4 maneiras de formar 5: 5, 2 + 2 + 1, 2 + 1 + 1 + 1 e 1 + 1 + 1 + 1 + 1.

Quando o guloso chega

Um sistema de moedas em que o guloso dá sempre o mínimo de moedas chama-se canónico. A maioria das moedas modernas é concebida assim, e em 1994 David Pearson descreveu um teste que verifica um sistema de moedas num número de passos que cresce apenas de forma polinomial com o número de moedas. As antigas moedas britânicas não eram canónicas: o guloso paga 48 pence com uma meia coroa, um xelim e um sixpence, quando bastariam dois florins.

Explore

Abra a aplicação, mude para a vista Tabela e prima Avançar. No modo Mínimo de moedas, a célula laranja é o montante a ser calculado e a célula azul é o montante mais pequeno que a moeda deixa; a linha de baixo guarda a última moeda, e no fim as moedas são lidas de volta ao longo dela. Mude para Número de maneiras e veja as contagens crescerem linha a linha à medida que cada moeda entra.

Perguntas frequentes

O problema do troco é um problema da mochila?

Um parente próximo. A variante do mínimo de moedas é um problema da mochila ilimitada em que cada moeda é um objeto cujo peso é o seu valor facial, a mochila tem de ficar cheia exatamente e o objetivo é usar o menor número de objetos.

Qual é a complexidade temporal?

O(k·A) para k tipos de moedas e um montante A, nas duas variantes. A tabela do mínimo de moedas tem A + 1 células, e a das maneiras (k + 1)·(A + 1), embora baste uma só linha se as células forem atualizadas no lugar.

Porquê contar as moedas numa ordem fixa?

Se cada montante experimentasse cada moeda, 1 + 2 e 2 + 1 seriam contadas como duas maneiras. Juntar as moedas uma linha de cada vez faz com que uma combinação seja sempre construída primeiro com as moedas anteriores, por isso cada uma é contada exatamente uma vez.

É possível ler as moedas de volta para o número de maneiras?

Não como uma resposta única, porque há muitas. A variante do mínimo de moedas guarda a última moeda de cada montante, o que basta para reconstruir uma combinação ótima.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar o problema do troco