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\}\)