Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

O que é o problema do troco e como resolvê-lo? A abordagem mais natural sempre funciona?

1 Resposta

+1 voto
respondida Jul 5 por Peng Yaohao (101 pontos)  
editado Jul 5 por Peng Yaohao

O problema do troco (coin change problem) consiste em encontrar a combinação com menor número de moedas cuja soma seja igual a uma quantia determinada, a partir de uma lista de moedas válidas que possuem disponibilidade infinita. Por exemplo, com as denominações padrão do Real brasileiro, há moedas para \(1\), \(5\), \(10\), \(25\), \(50\) e \(100\) centavos: o objetivo é, dada uma quantia (número inteiro, em centavos), encontrar o "caminho" que fornece essa quantia com a menor quantidade de moedas válidas. Esse problema é bastante similar ao chamado problema da mochila, no qual se busca a alocação de objetos que maximiza o valor de uma mochila com uma restrição de peso, dados os pesos e valores de cada objeto; o problema do troco seria o da mochila "ao contrário": dado um valor fixo para a mochila, encontrar a combinação de objetos com menor peso que fornece esse valor.

É imediato observar que, para qualquer quantia \(n\in\mathbb{N}\) sempre há uma solução possível, relativo à alocação de \(n\) moedas de \(1\) centavo; claro, essa solução não é nem um pouco elegante, tampouco natural. A maneira natural de solucionar esse problema é a chamada abordagem gananciosa (greedy algorithm), que, conforme o nome insinua, consiste em alocar a máxima quantidade possível da moeda de denominação mais alta, recursivamente até que a quantia seja atingida (curiosamente, em várias traduções aparece como "algoritmo guloso"...).

Ilustrando com um caso simples em que a quantia \(n=68\) centavos, a abordagem gananciosa seria: começar pela moeda de maior valor e alocá-la até que o valor dessa moeda seja maior que a quantia remanescente. Nesse caso, a moeda de maior valor vale \(1\) real (\(100\) centavos), maior que \(n\); como não faz sentido o troco ser maior que a quantia, passa-se para a próxima moeda, a de \(50\) centavos, e alocamos-a até que a quantia restante seja menor que \(50\) centavos. É fácil ver que iremos designar uma moeda de \(50\), restando assim \(18\) centavos, e repetimos o processo até que o troco se zere. Para \(18\) centavos, a moeda de \(25\) centavos não serve (\(25>18\)), então alocamos 1 moeda de \(10\) centavos, restando \(8\); daí, designamos uma de \(5\) e três de \(1\), totalizando \(68\) centavos (\(68=50+10+5+1+1+1\)). Assim, pelo algoritmo ganancioso, o troco de \(68\) centavos será composto por \(6\) moedas.

Mas será que a versão gananciosa sempre é a melhor? A resposta é: não!. Para o caso da lista de moedas válidas no Brasil ilustrada anteriormente, a versão gananciosa funciona bem, mas imagine um sistema fictício com apenas três tipos de moedas: \(1\) centavo, \(7\) centavos e \(10\) centavos: veja como o algoritmo ganancioso falha para o caso em que o troco é \(n=14\) centavos -- alocando uma moeda de \(10\) centavos, restam \(4\) centavos, que precisarão ser preenchidas com quatro moedas de \(1\) centavo, totalizando \(5\) moedas. Essa claramente não é a melhor alocação, visto que seria melhor dar o troco com duas moedas de \(7\) centavos!

Como podemos contornar essa limitação da "ganância"? Intuitivamente vemos que escolher uma moeda de \(10\) centavo não é a melhor escolha se olharmos para o "longo prazo", pois cada escolha de moeda condiciona a escolha ótima do futuro -- escolher uma de \(10\) centavos parece ser interessante numa perspectiva "míope", mas acaba forçando pegar mais quatro de \(1\) centavo; pegar uma de \(7\) centavos abre mão de uma quantidade da moeda de valor maior, mas visando a uma melhor escolha a longo prazo, pois nesse caminho é preciso pegar somente mais uma moeda (em vez de quatro). A essa abordagem se chama de programação dinâmica, que consiste em otimizar uma recompensa ("função objetivo") ao longo do tempo, buscando um ótimo "geral", em vez de se preocupar meramente com o ganho imediato. Para os entusiastas em xadrez, essa partida magnífica de Morphy ilustra bem essa ideia: abrir mão de peças para conduzir seus dois adversários a uma derrota fulminante e extremamente poética...

Voltando para o problema do troco, como podemos implementar uma solução baseada em programação dinâmica? Basicamente, a ideia é encontrar a resposta mais eficiente para cada troco possível \(n^*\in\{0,1,2,...,n\}\), partindo de um caso base (no nosso caso, aquela solução ingênua onde todo o troco é dado com moedas de \(1\) centavo), e com isso encontrar recursivamente a sequência ótima que leva a um troco total de \(n\). Partindo de uma lista de \(k\) moedas válidas \(\mathcal{M}=\{m_1,m_2,...,m_k\}\), o algoritmo irá encontrar qual moeda deve ser escolhida para se encontrar o melhor caminho que leva a um troco \(n^*\), e repetir para todos os \(n^*\) até chegar no caso \(n^*=n\), que é o caso desejado. Para cada \(n^*\), como é conhecido que uma solução possível é "\(n^*\) moedas de \(1\) centavo", atribui-se moedas factíveis (ou seja, moedas válidas \(\in\mathcal{M}\) e que sejam menores que \(n^*\), pois caso contrário "estouraria" a quantia imediatamente); após testar para cada moeda factível, armazenar a moeda que induz a sequência com menor quantidade de moedas necessárias para se completar \(n^*\), e assim sucessivamente, até que se chegue em \(n\).

Mas qual é a diferença desse algoritmo para a abordagem gananciosa? A diferença fundamental está no fato de a escolha ótima "local" para \(n^*\) depende do caminho que essa escolha irá condicionar -- ou seja, escolhendo uma de \(10\) centavos para um troco de \(14\) fará com que o \(n^*\) remanescente seja \(4\), e portanto o caso em que \(n^*=4\) precisará também ser avaliado! É como se fossem vários "cenários futuros" possíveis (o jargão para isso é "estados"), e escolhe-se aquele cuja resposta ótima seja menos custosa. Nesse nosso caso, os "futuros" possíveis são \(14-1=13\), \(14-7=7\) e \(14-10=4\) -- sabendo que a escolha da primeira moeda irá certamente fazer com que o troco remanescente seja \(13\), \(7\) ou \(4\), avaliar os três casos em que \(n^*\) é \(13\), \(7\) ou \(4\), cada um desses casos, por sua vez, induzem diferentes "futuros", e assim sucessivamente...

Dessa forma, a programação dinâmica irá fornecer um vetor de respostas ótimas locais para todo \(n^*\), onde "ótima" se refere à quantidade mínima de moedas necessárias para se completar o troco da quantia \(n^*\), com a restrição de não se usar nenhuma moeda cujo valor unitário seja maior que \(n^*\). Para cada um dos "futuros" possíveis, bastaria invocar o respectivo elemento no vetor previamente armazenando, o que poupa realizar cálculos desnecessários (o que aconteceria caso simplesmente utilizássemos uma recursão). Paralelamente, alocamos um vetor de contadores, para assim termos controle da quantidade de moedas e da moeda que deve ser escolhida imediatamente para qualquer \(n^*\); para fazer o caminho completo de \(n^*=n\), bastaria começar com \(n\) e pegar iterativamente a moeda ótima com \(n^*\) sendo a diferença entre \(n\) e a moeda \(m_i\) retirada, repetindo o processo até zerar o troco.

Seguem implementações em Python das versões gananciosa e programação dinâmica:

def ganancioso(valores,quantia): # pressupõe que a lista de moedas válidas está em ordem decrescente
    guloso=[] # lista vazia
    for k in range(0,len(valores)):
        while valores[k]<=quantia: # colocar moeda até que seu valor seja maior que o troco restante
            guloso.append(valores[k]) # guarda na lista
            quantia=quantia-valores[k] # atualiza troco restante
    print(guloso)

def DonPython(moedas_validas,troco,cont,resp_local):
    for i in range(1,troco+1): # range dos n*'s
      contador=i
      qual_pegar=1 # caso base: troco todo em moeda de 1 centavo
      for j in moedas_validas:
          if j<=i: # não continua se moeda tiver valor maior que n*
              if cont[i-j]+1<contador: # tira moeda 'i' do total; se quantidade ótima para troco de n* for menor que o minimo provisório:
                  contador=cont[i-j]+1 # atualizar quantidade ótima
                  qual_pegar=j # qual moeda escolher para minimizar quantidade exigida para troco de n*
          cont[i]=contador # armazena na tabela os trocos ótimos para todos os n*'s
          resp_local[i]=qual_pegar # para todo n*, qual moeda 'marginalmente' deve ser escolhida?
   print(cont[troco]) # função retorna quantidade ótima para o 'n' original

def caminho(resp_local,troco): # quais moedas efetivamente pegar
    moedas=[] # lista vazia
    while troco>0: # repetir até zerar troco
        devo_pegar_essa=resp_local[troco] # qual moeda escolher dado 'n'?
        moedas.append(devo_pegar_essa) # guarda essa moeda na lista
        troco=troco-devo_pegar_essa # atualiza troco, diminuindo valor da moeda escolhida
    print(moedas) # função retorna quais moeda são selecionadas

Observe que, para as denominações usuais do Real Brasileiro, os dois algoritmos fornecem a mesma resposta:

quantia=68
lista=[100,50,25,10,5,1]
resp_local=[0]*(quantia+1)
contador=[0]*(quantia+1)

ganancioso(lista,quantia) # moedas escolhidas pela estratégia gananciosa

DonPython(lista,quantia,contador,resp_local)
caminho(resp_local,quantia) # moedas escolhidas pela estratégia programação dinâmica

Em contrapartida, naquele sistema fictício em que as moedas válidas são \(1\), \(7\) e \(10\) centavos, a versão gananciosa nem sempre é a melhor opção:

quantia=35
lista=[10,7,1]
resp_local=[0]*(quantia+1)
contador=[0]*(quantia+1)

ganancioso(lista,quantia) # moedas escolhidas pela estratégia gananciosa

DonPython(lista,quantia,contador,resp_local)
caminho(resp_local,quantia) # moedas escolhidas pela estratégia programação dinâmica

Note que o algoritmo ganancioso fornece uma solução com \(8\) moedas: \(\{10,10,10,1,1,1,1,1\}\); enquanto que a versão por programação dinâmica dá um caminho com apenas \(5\) moedas: \(\{10,10,7,7,1\}\)

Veja a diferença entre as estratégias a partir de mais um sistema fictício de moedas válidas:

quantia=66
lista=[47,29,13,7,4,1]
resp_local=[0]*(quantia+1)
contador=[0]*(quantia+1)

ganancioso(lista,quantia) # moedas escolhidas pela estratégia gananciosa

DonPython(lista,quantia,contador,resp_local)
caminho(resp_local,quantia) # moedas escolhidas pela estratégia programação dinâmica

A versão gananciosa fornece um caminho com \(5\) moedas: \(\{47,13,4,1,1\}\); enquanto que o caminho do "DonPython" só exige \(4\) moedas: \(\{29,29,7,1\}\)

comentou Jul 6 por João Gabriel Souza (76 pontos)  
Resolução do exercício excelente: muito bem explicado, a resolução ficou bem didática, exemplos muito bem determinados. A exemplificação da Programação Dinâmica feita com uma jogada de xadrez foi muito legal e facilitou o entendimento do exercício.  O jogo entre Paul Morphy vs Duke Karl. O exercício está correto e replicável.

Apenas como sugestão ao código: nos resultados dos exemplos entre estratégia gananciosa e programação dinâmica, os resultados mostram apenas o número de moedas para a estratégia de programação dinâmica e não apresentam os resultados para estratégia gananciosa.

O comentário serve só como sugestão, pois não altera o resultado.
...