Programação Dinâmica

Algoritmos e Programação de Computadores II

Prof. MSc. Leanderson André

leandersonandre@univille.br

Universidade da Região de Joinville

Programação Dinâmica

Definição

Técnica de Design de Algoritmo que pode ser utilizada pra encontrar soluções ótima para problemas e contar o número de soluções.

Problema do Troco

Dado um conjunto de moedas = {c₁,c₂,…c_k} e uma quantidade dinheiro alvo n, encontre a menor combinação de moedas que somados resulta na quantidade n.

Moedas do real brasileiro

Problema do Troco

Exemplo: moedas = {1,2,5}, alvo = 12.

Qual é a solução ótima?

3 moedas
5 + 5 + 2 = 12

Problema do Troco

Exemplo: moedas = {1,2,5}, alvo = 12.

Qual foi a estratégia adotada?

Selecione sempre a maior moeda sem exceder o valor da soma.
Algoritmo guloso

Problema do Troco

Exemplo: moedas = {1,3, 4}, alvo = 6.

Qual é a solução ótima?

Algoritmo guloso: 3 moedas: 4 + 1 + 1 = 6
Solução ótima: 2 moedas: 3 + 3 = 6

Problema do Troco

Algoritmos gulosos não garantem a solução ótima.

Algoritmos de força bruta garantem a solução ótima por explorar todas as possibilidades, mas podem ser muito lentos para uma grande quantidade de dados de entrada.

Qual é a alternativa?

A programação dinâmica pode encontrar a solução ótima como a força bruta mas sendo eficiente.

Procurando a solução ótima

O problema pode ser reformulado de maneira recursiva para encontrar a solução para os seus subproblemas.

Por exemplo: moedas = {1,3,4}

Expressão	Valor	Expressão	Valor
`resolver(0)`	0	`resolver(6)`	2
`resolver(1)`	1	`resolver(7)`	2
`resolver(2)`	2	`resolver(8)`	2
`resolver(3)`	1	`resolver(9)`	3
`resolver(4)`	1	`resolver(10)`	3
`resolver(5)`	2

A propriedade essencial de resolver é que seus valores podem ser calculadas recursivamente para os valores menores.
Por exemplo: moedas = {1,3,4}

resolver(x) = min(resolver(x-1) + 1,
                  resolver(x-3) + 1,
                  resolver(x-4) + 1)

O caso base da recursão é resolver(0) = 0.

Chamadas recursivas do algortimo

A cada nível, uma moeda é utilizada.

Chamadas recursivas do algortimo

Caminhos das soluções possíveis.

Solução

Por exemplo: moedas = {1,3,4}, soma = 10

resolver(10) = resolver(7) + 1  // x - 3
             = resolver(4) + 2  // x - 2
             = resolver(0) + 3  // x - 4     
             = 3

Algoritmo recursivo

$$ \operatorname{resolver}(x)= \begin{cases} \infty, & x < 0 \\ 0, & x = 0 \\ \displaystyle\min_{c \in \text{moedas}} \left\{\operatorname{resolver}(x-c)+1\right\}, & x > 0 \end{cases}$$

Exercício

Codifique a solução recursiva para o problema do troco utilizando a linguagem Python.

Entrada: moedas = {1,3,4}, x = 10

Saída: 3

Solução

def resolver(soma,moedas):
    if soma < 0:
        return float('inf')
    if soma == 0:
        return 0
    menor = float('inf')
    for m in moedas:
        r = resolver(soma-m, moedas)
        menor = min(menor,r)
    return menor

moedas = [1,3,4]
resultado = resolver(10,moedas)
print("Resultado:",resultado)

Prof. MSc. Leanderson André

leandersonandre@univille.br

Universidade da Região de Joinville