UVa 674: Coins Change

A descrição do problema encontra-se aqui: 674.pdf. A primeira vista está semelhante com o problema UVa166 (Making Change) mas enquanto no segundo o objectivo era encontrar o número mínimo de moedas para fazer o troco, neste problema é necessário calcular o número de maneiras de fazer o troco.

Se o troco for 6 cents, existem duas maneiras de fazer o troco: 5 + 1 ou 1 + 1 + 1 + 1 + 1 + 1 mas 1 + 5 não é diferente de 5 + 1. Para evitar contar mais de uma vez a mesma combinação vamos considerar as moedas na ordem decrescente de valor.

• Se temos um troco de x cents vamos tentar subtrair o valor da maior moeda:
  1. Se x < 50 então vamos tentar a moeda seguinte (25c):
  2. Se x >= 50 o troco que sobra é x - 50c. Agora podemos:
     1. subtrair 50c e experimentar outra vez a mesma moeda
     2. experimentar com a moeda de valor imediatamente inferior (25c).

Este algoritmo é recursivo. Podemos usar uma função que recebe a moeda «corrente» ou a moeda a testar e o valor do troco:

solve(iCoin, value)   // iCoin é o índice da moeda num array coins = {50, 25, 10, 5, 1}; value corresponde ao troco

A função deve retornar o número de maneiras de conseguir aquele valor de troco. Como vamos subtraindo ao valor do troco, quando value vale 0 encontramos mais uma maneira, neste caso o valor retornado será 1.

Os passos 2.1 e 2.2 correspondem a duas chamadas recursivas à função. O resultado dessas chamadas deve ser adicionado porque procuramos o numero total de maneiras de conseguir fazer o troco. Ficamos portanto com :

solve(iCoin, value) 
    if (value == 0) return 1
    diff = value - coins[iCoin]
    return solve(iCoin, diff) + 
           solve(iCoin + 1, value)

Esta solução é obviamente incompleta. O que acontece quando o valor de value for negativo ? Quando já experimentamos todas moedas ? Vamos em ambos os casos retornar 0 (são combinações de moedas que não permitem fazer o troco) e naturalmente não fazemos chamadas recursivas :

solve(iCoin, value) 
    if (value == 0) return 1
    if (value < 0 || iCoins == coins.length)
       return 0
    diff = value - coins[iCoin]
    return solve(iCoin, diff) + 
           solve(iCoin + 1, value)

Pode implementar esta solução mas não passará o teste no site do UVa ! É muito ineficiente e os mesmos valores podem vir a ser calculados várias vezes. A solução consiste em usar programação dinâmica. A medida que são calculados os valores da função solve podem ser guardados numa tabela e reutilizados quando necessário. É preciso notar que os valores da função dependem de dois parâmetros será portanto necessário usar uma tabela de duas dimensões:

solve(iCoin, value) 
    if (value == 0) return 1
    if (value < 0 || iCoins == coins.length)
       return 0
    if (solutions[iCoins][value] != 0) 
       return solutions[iCoins][value]
    diff = value - coins[iCoin] 
    count = solve(iCoin, diff) + 
           solve(iCoin + 1, value)
    solutions[iCoins][value] = count
    return count

Pode agora implementar a solução em Java e submete-la no site do UVa.