O Problema do Troco

O problema do troco é, como a Soma de Sub-Conjuntos, um parente do problema da mochila (Knapsack). O problema em se resume em como obter um determinado valor com o menor número possível de moedas (ou notas), respeitando os valores das moedas (ou notas) disponíveis.

Uma apresentação formal pode ser encontrada na Wikipedia, mas sem uma descrição detalhada da solução.

A Solução Gananciosa

Quando nos defrontamos com este tipo de problema no nosso dia-a-dia, costumamos usar uma "solução ganaciosa" (greedy solution): partimos da moeda de maior valor para a de menor valor, usando o máximo possível de cada vez.

Por exemplo, para obter R$0,73 com as nossas moedas de 50, 25, 10, 5 e 1 centavos pegamos 1 moeda de 0,50 duas de 0,10 e 3 de 0,01.

Dependendo do valor das moedas, esta solução pode não ser a ótima. Pegando dois exemplos:

• Se quisermos obter o valor 6 com moedas de 4, 3 e 1, o método "ganancioso" leva a três moedas (4, 1 e 1) ao invés da solução ótima de duas moedas de 3.
• Se quisermos obter o valor 37 com moedas de 20, 15, 10 e 7, o método "ganancioso" falhará após pegar uma moeda de 20 e outra de 15, apesar do valor poder ser obtido com uma moeda de 20, uma de 10 e uma de 7.

Existe um algorítimo para determinar se o método "ganancioso" funciona para um determinado conjunto de valores de moeda, detalhes nos links no final.

Programação Dinâmica

Nesta solução, vamos gerar os valores possíveis de serem obtidos iterativamente, considerando inicialmente apenas a primeira moeda e acrescentando uma moeda de cada vez. É algo parecido com o que fizemos no problema da soma de sub-conjuntos. A teoria por trás está no livro de Martello e Tooth (que você pode baixar gratuitamente, links no final).

O problema que queremos resolver é como obter o valor m utilizando moedas com n valores v[i] (i variando de 0 a n-1). Para isto vamos montar um vetor f[c] onde cada posição indica a quantidade mínima de moedas para gerar o valor c (INFINITO indica que o valor não pode ser gerado). Nos interessa montar o vetor f com c variando de 0 até m. A nossa resposta final estará em f[m].

Começamos considerando somente uma moeda (v[0]). Neste caso é possível gerar apenas os valores múltiplos dela:

for (c = 1; c <= m; c++)
 f[c] = INFINITO;
for (j = 0, c = 0; c <= m; j++, c += v[0])
 f[c] = j;

Vamos agora considerar que já temos f preenchido para as primeiras i-1 moedas e queremos atualizá-lo para considerar a moeda i. Vamos atualizar o vetor variando c de v[i] a m (os valores abaixo de v[i] obviamente não são afetados), acrescentando uma moeda v[i] por vez. O novo valor de f[c] será o mínimo entre:

• f[c-v[i]]+1, correspondente a usar uma moeda v
  
• O valor atual de f[c] (ou seja, não compensa usar a moeda v[i])

Antes de ver o código, vamos ver como isto funciona procurando gerar o valor 6 com moedas de valor 1, 3 e 4:

0 1 2 3 4 5 6 - começando com a moeda de valor 1
0 1 2 1 2 3 2 - acrescentando a moeda de valor 3
0 1 2 1 1 2 2 - acrescentando a moeda de valor 4

Uma última otimização pode ser feita, se os valores v[i] estiverem em ordem crescente. Ao invés de atualizar f[c] para c de v[i] a m, podemos parar no mínimo entre m e v[i]*v[i+1], já que v[i] moedas de valor v[i+1] gera o valor v[i]*v[i+1] com menos que v[i+1] moedas de valor v[i].

O código fica assim:

for (j = 1; j < n; j++)
{
  if (j == (n-1))
    l = m;
  else
  {
    l = v[j]*v[j+1];
    if (l > m)
      l = m;
  }
  for (c = v[j]; c <= l; c++)
  {
    x = fm[c - v[j]] + 1;
    if (x < fm[c])
      fm[c] = x;
  }
}

Links

O livro "Knapsack Problems" de Silvano Martello e Paolo Tooth pode ser baixado do link abaixo, o capítulo sobre o problema do troco é o quinto.
http://www.or.deis.unibo.it/knapsack.html

A tese abaixo (Algorithms for Knapsack Problems de David Pisinger) não menciona especificamente o problema do troco, mas fala de algorítimos mais avançados para os problemas Knapsack:
http://www.diku.dk/users/pisinger/95-1.pdf