DP - Problema do Troco em Moedas

Este problema pode ser enunciado como:

Dado um valor de troco N (um número inteiro no nosso exemplo).
Nós temos suprimento infinito de cada tipo de moeda do conjunto S = {S1, S2, .., SM}.
Note que temos portanto M tipos de moedas e teoricamente temos infinitas delas.
Quantas maneiras podemos combinar as moedas para obter um troco exato?
A ordem das moedas não importa.

Por exemplo temos que dar um troco de N = 4 dinheiros.
O conjunto de moedas que temos é S = {1,2,3}.
Podemos ver que existem quatro soluções: {1,1,1,1}, {1,1,2}, {2,2}, {1, 3}.
Assim a resposta do programa deve ser 4.

Este problema pode ser resolvido por DP. Identificamos as duas características:

1) Subestrutura ótima

Para contar soluções, podemos dividir todas as soluções em dois subconjuntos:
a) Todas as soluções que não contêm moeda "i" (ou seja Si).
b) As soluções que contêm pelo menos uma moeda Si.
Desta forma podemos escrever o problema de contagem como

C(S, n) = C(S', n) + C(S, N-Si)

Onde S' = S - {Si}

Desta forma vemos que o problema tem a propriedade subestrutura ótima como o problema pode ser resolvido usando soluções de subproblemas. A equação e as condições abaixa deixam claro também que os problemas são sobrepostos.

Temos que notar que existem algumas condições:

a) C(S,0) = 1, pois se n=0 existe uma solução que não precisa de mais moedas
b) C(S,n) = 0, se n<0, pois n negativo, não há uma solução do problema (subtraiu demais)
c) C(S,n) = 0, se S = {} e n > 0, pois se não temos moedas para dar um troco "n" (já que n é maior que zero), não tem como acharmos uma solução.

O que falta no exemplo acima? Se você falou a memorização dos dados... acertou!

A memorização aumenta bastante a velocidade, uma vez que não precisamos recalcular.

Programação Dinâmica

Em computação a programação dinâmica é um método utilizado para a construção de algoritmos capazes de resolver problemas computacionais. Este método é aplicável aos problemas cuja solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada.
A solução anterior é memorizada para evitar recálculo.
Desta forma a programação dinâmica ou DP (Dynamic Programming) resolve um problema a partir de subproblemas que sobrepostos compõem o problema original.

Um problema computacional pode ser resolvido por DP se possuir duas características denominadas (1) subestrutura ótima e (2) superposição de subproblemas. Um problema apresenta uma subestrutura ótima quando uma solução para o problema contém em seu interior soluções para subproblemas - isto é temos a mesma fórmula de recorrência. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes - é aí que entra a memorização.

A DP não é uma forma intuitiva de pensar, portanto temos que ver diversos exemplos para conseguir compreender e assimilar como ela trabalha. Vou criar a partir de agora um conjunto de posts que mostram como solucionar alguns problemas usado DP. Estes posts virão com uma implementação completa em Java para o problema. O primeiro da série busca descobrir de quantas maneiras é possível dar um troco (N) utilizando um determinado conjunto de moedas.