O problema do Troco

O problema do Troco é um problema clássico da ciência da computação. O fato do problema ser clássico torna um pouco raro a sua aparição em competições atuais, uma vez que não seria novidade, porém nada impede que problemas mais complexos baseados nesse problema apareçam, e nada melhor que saber resolver o problema original.

Neste post vou falar sobre as duas soluções mais comuns: a solução Gulosa e a solução usando Programação Dinâmica.

Clique no link abaixo para ver o resto do post.

Descrição:

Imagine que você trabalha no caixa de um supermercado. Sempre que um cliente chega e paga sua compra, você deve entregar a ele o troco em moedas. Você particularmente gosta dessas moedas, e quer entregar o menor número de moedas possível ao cliente.

Para um valor de troco N, e com um estoque infinito de cada uma das M moedas de diferentes valores m1, m2, …, mM, quais e quantas moedas você deve entregar ao cliente de modo que o total de moedas seja o mínimo possível?

Por exemplo, se você conta com um estoque infinito de moedas de valor M = {1, 2, 8, 14, 25}, e precisa entrega um troco igual a N = 28, há diversas maneiras de se montar as combinações:
{25, 2, 1}, com um total de 3 moedas.
{14, 14}, com um total de 2 moedas.
{14, 8, 2, 2, 2}, com um total de 5 moedas.
{…}, entre outros.

Há duas soluções bem comuns para se resolver este problema.

Solução Gulosa:

Uma solução Gulosa, pela sua definição, consiste em fazer a melhor escolha no estado atual. No problema do Troco, qual parece ser a melhor opção?
Temos um valor N, e quando escolhemos uma moeda m para subtrair de N, desejamos que N fique o mais próximo possível de 0. Se ele ficar igual a 0, por exemplo, terminamos.

Digamos que N = 12, e M = {1, 2, 5}. De acordo com a estratégia citada acima, a melhor opção parece ser a moeda de valor 5, pois ela é a moeda de maior valor e também a que me faz ficar mais próximo de 12. Em seguida, podemos adicionar denovo a moeda de valor 5, totalizando 2 moedas e um valor total igual a 10. Por fim, podemos adicionar a moeda de valor 2, resultando em 3 moedas que somam 12 (a saber, 5, 5 e 2).

No caso atual, com 3 moedas nós podemos dar um troco de valor N. Há como fazer melhor que isso? Não!
Então essa estratégia é ótima? Nem sempre!

Digamos agora que N = 8, e M = {1, 4, 6}. De acordo com a estratégia citada, iríamos pegar, respectivamente, as moedas de valores 6, 1 e 1, com um total de 3 moedas.
Há, porém, uma estratégia melhor: as moedas de valores 4 e 4, com um total de 2 moedas.

Conclusão: A solução gulosa nem sempre é ótima.
Sendo mais específico, a solução gulosa só é ótima quando os valores de moedas disponíveis atende os requisitos de uma sequência canônica.
Para maiores detalhes, pesquise por referências e provas sobre isso na internet.

(Experimental) Abaixo está uma demonstração do resultado do algoritmo guloso. Faça seus testes mudando o valor de N e das moedas:

Valor de N: Moedas
Total:
Algoritmo Guloso: 0 0 0 0 0 0 0 0
Solução Ótima: 0 0 0 0 0 0 0 0

Segue o código da solução Gulosa em C++, apenas para referência:

// função que recebe o valor de troco N, o número de moedas disponíveis M,
// e um vetor com as moedas disponíveis m
// essa função deve retornar o número mínimo de moedas, de acordo com a estratégia gulosa
int num_moedas(int N, int M, int * m) {
    int total = 0;

    // vamos supor que o vetor m esteja ordenado em ordem crescente
    // portanto, a moeda de maior valor está no final do vetor
    for(int i=M-1; i>=0; i--) {
        int aux = N/m[i]; // número de moedas de valor m[i]
        N -= aux * m[i]; // subtrai-se esse valor de N
        total += aux;
    }

    return total;
}

Solução com Programação Dinâmica:

A Programação Dinâmica, conforme eu brevemente descrevi neste post [link], pode ser definida e resolvida utilizando o conceito de problema principal e sub-problemas:

  • Problema principal é o problema objetivo, aquele o qual queremos saber a resposta.
  • Sub-problema é um problema semelhante ao problema principal. Ele não é o problema objetivo, mas a sua resolução pode ajudar na resolução do problema objetivo.

Qual o nosso problema principal? Descobrir o número mínimo de moedas a se usar para devolver um troco de valor igual a N.
E qual pode ser nosso sub-problema? Se ele é semelhante ao problema principal, podemos tentar: Descobrir o número mínimo de moedas a se usar para devolver um troco de valor igual a J, para todo 0 <= J < N.

Diferente do problema Lajotas Hexagonais que eu descrevi aqui [link], o relacionamento entre os sub-problemas não é tão trivial.

Seja o problema principal N, e sejam as duas moedas disponíveis m1 e m2. Se eu adicionar a moeda m1 na solução, caímos no sub-problema Nm1; Se eu adicionar a moeda m2 na solução, caímos no sub-problema Nm2.

Qual escolhemos? Já vimos que escolher a maior moeda não é uma boa estratégia. A solução aqui é comparar as duas possibilidades.
Quais dos sub-problemas custa menos moedas para ser resolvido, Nm1 ou Nm2?

Não sabemos, então precisamos resolvê-los. Ok, vamos resolver o sub-problema Nm1. Podemos adicionar a moeda m1 na solução, e cairemos no sub-problema Nm1m1; Podemos adicionar a moeda m2 na solução, e cairemos no sub-problema Nm1m2. O mesmo vale para a duas opções no sub-problema Nm2, Nm1m1m1, e por aí vai.

Quando isso acaba? Aqui entra o caso base.
Quando N = 0, terminamos, pois se eu preciso entregar o valor 0 de troco, eu simplesmente não entrego nada, e isso me custa 0 moedas.
Quando N < 0, há algo errado na solução, pois estamos devolvendo mais troco que o requisitado. Evitaremos então cair nesse sub-problema.

Formalmente para esse caso em particular com duas moedas, seja dp[N] o menor número necessário de moedas para se resolver o sub-problema em N, temos:
dp[N] = min(dp[N-m1], dp[N-m2]) + 1

Escolhemos a solução que custa menos moedas, e somamos 1, pois estamos usando essa moeda para chegar na solução usada.

Precisamos ainda de um caso mais geral, onde temos mais que duas moedas a disposição:
dp[N] = min(dp[N-m])+1,
para todo m que pertence ao conjunto M, e N-m >= 0

(Experimental) Seja N = 6, e M = {1, 3, 4}, temos:
(passe o mouse pelas células de dp[N] para ver os relacionamentos)

N 0 1 2 3 4 5 6
dp[N] 0 1 2 1 1 2 2

E segue o código da solução em C++, para referência:

// função que recebe o valor de troco N, o número de moedas disponíveis M,
// e um vetor com as moedas disponíveis m
// essa função deve retornar o número mínimo de moedas,
// de acordo com a solução com Programação Dinamica.
int num_moedas(int N, int M, int * m) {
    int dp[N+1];

    // caso base
    dp[0] = 0;

    // sub-problemas
    for(int i=1; i<=N; i++) {
        // é comum atribuir um valor alto, que concerteza
        // é maior que qualquer uma das próximas possibilidades,
        // sendo assim substituido
        dp[i] = 1000000;

        for(int j=0; j<M; j++) {
            if(i-m[j] >= 0) {
                dp[i] = min(dp[i], dp[ i-m[j] ]+1);
            }
        }
    }

    // solução
    return dp[N];
}

Espero que tenha ficado claro.

Eu adicionei algumas tabelas interativas para exemplificar os casos, espero que tenha funcionado e tenha tido um efeito positivo. Qualquer sugestão é bem vinda.

Referências:
http://wpattern.com/blog/post/2012/03/24/Problema-do-Troco-Analise-de-Algoritmos.aspx
http://dqsoft.blogspot.com.br/2010/04/o-problema-do-troco.html
http://www.or.deis.unibo.it/knapsack.html

Exercícios:
http://br.spoj.com/problems/MOEDAS/
http://www.urionlinejudge.com.br/judge/pt/problems/view/1034
http://br.spoj.com/problems/TROCO13/

9 ideias sobre “O problema do Troco”

  1. Parabéns pela iniciativa de compartilhar o conhecimento. Vou começar a me preparar para a maratona de programação. Suas dicas tanto nesse blog quanto no blog passado com certeza vão me ajudar bastante.

  2. Olá Cristian Bonilha,

    Na sua solução por dp está
    if(N-m[j] >= 0) {
    dp[i] = min(dp[i], dp[ N-m[j] ]+1);
    }
    mas o correto é:
    if(i-m[j] >= 0) {
    dp[i] = min(dp[i], dp[ i-m[j] ]+1);
    }
    Abraços.

  3. Olá, gostaria de tirar uma dúvida, primeiramente o que seria um sequência canônica? se a minha sequência é canônica eu tenho certeza de que o algoritmo guloso funciona?
    Mais uma… Será que eu consigo juntar esses dois códigos para obter maior velocidade ?
    Obrigado…!

  4. Curto e grosso: para resolver o problema moedas do spoj crie um vetor com 50000 posições. O índice desse vetor vai ser o preço (o spoj chama de “m”) . A posição zero vai conter zero. Suponha que as moedas disponíveis sejam 6 e 13. O conteúdo da posição 57, p.ex., vai ser um mais a posição 57-6 ou 57-13, a que for menor ou impossível, se ambas forem impossíveis.
    Algo do tipo 1 + qm[i – v[j]], onde qm é o vetor. No exemplo, i=57, v o vetor com os valores das moedas, 6 e 13.

  5. Olá!

    E quanto a disposição das moedas, como eu poderia implementar isso de forma inteligente? Como em uma máquina de refrigerante, por exemplo..O troco pode ser de R$ 2,00..O que eu facilmente entregaria duas moedas de R$ 1,00. Mas talvez a máquina só tenha uma moeda de R$ 1,00, então eu teria que entregar uma moeda de R$ 1,00 e duas de R$ 0,50. E talvez a máquina nem tenha duas de R$ 0,50, apenas uma. Nesse caso o troco ficaria 1 moeda de R$ 1,00, 1 moeda de R$ 0,50 e duas de R$ 0,25. E assim sucessivamente, até ele não conseguir entregar o troco por falta de moedas e assim sendo, informar o usuário para escolher outro refrigerante ou de repente devolver todo dinheiro colocado na máquina para não haver prejuízos.

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *