Projeto e Análise de Algoritmos  
Aula 05 Técnicas de Projeto de Algoritmos  
(Programação Dinâmica)  
Edirlei Soares de Lima  
<edirlei@iprj.uerj.br>  
Estratégias de Projeto de Algoritmos  
Força Bruta (Brute Force)  
Dividir e Conquistar (Divide and Conquer)  
Diminuir e Conquistar (Decrease and Conquer)  
Transformar e Conquistar (Transform and Conquer)  
Compromisso TempoEspaço (Space and Time Tradeoffs)  
Estratégia Gulosa (Greedy)  
Programação Dinâmica (Dynamic Programming)  
Voltando Atrás (Backtracking)  
Ramificar e Limitar (Branch and Bound)  
Algoritmos Aproximados  
Programação Dinâmica  
A programação dinâmica tem como objetivo reduzir  
o tempo de execução de um programa utilizando  
soluções ótimas a partir de subproblemas  
previamente calculados.  
Resolvem-se os problemas de pequena dimensão e  
guardam-se as soluções;  
A solução de um problema é obtida combinando as de  
problemas de menor dimensão.  
Programação Dinâmica  
Passos gerais de um algoritmo baseado em Programação  
Dinâmica:  
Dividir o problema em sub problemas;  
Computar os valores de uma solução de forma bottom-up e  
armazená-los (memorização);  
Construir a solução ótima para cada subproblema utilizado os valores  
computados.  
Quando usar Programação Dinâmica?  
Quando a solução ótima de um subproblema pode ser composta pelas  
soluções ótimas dos subproblemas;  
Quando o calculo da solução ótima implica muitas vezes no calculo do  
mesmo subproblema.  
Exemplo 1: Série de Fibonacci  
Série de Fibonacci:  
0
ꢁꢂ ꢃ = 1  
ꢄꢅ ꢃ = 0  
ꢄꢅ ꢃ = 1  
ꢁꢂ ꢃ − 1 + ꢀꢁꢂ − 2 ꢄꢅ > 1  
Algoritmo Simples:  
1
2
3
4
5
. Fibonacci(n)  
. se n < 2 então  
. retorne n  
. senão  
O(2n)  
. retorne fibonacci(n 1) + fibonacci(n 2)  
Exemplo 1: Série de Fibonacci  
Algoritmo Simples:  
1
2
3
4
5
. fib(n)  
.
.
se n < 2 então  
retorne n  
. senão  
.
retorne fib(n 1) + fib(n 2)  
fib(5)  
fib(4)  
fib(3)  
fib(3)  
fib(2) fib(2)  
fib(1)  
Problema: repetição de chamadas!  
fib(2)  
fib(1)  
Exemplo 1: Série de Fibonacci  
Algoritmo Baseado em Programação Dinâmica:  
1
2
3
4
5
6
7
8
9
. fib(n)  
O(n)  
. se n < 2 então  
. retorne n  
. senão  
. V[0] 0  
. V[1] 1  
. para i ← 2 até n faça  
.
V[i] ← V[i-1] + V[i-2]  
. retorne V[i]  
Exemplo 2: Problema da Mochila  
Dados n itens:  
Pesos: w1, w2, ..., wn  
Valores: v1, v2, …, vn  
Uma mochila de capacidade W  
Problema: encontrar o subconjunto mais valioso de  
itens que caibam dentro da mochila (Knapsack  
Problem).  
Exemplo 2: Problema da Mochila  
Problema: encontrar o subconjunto mais valioso de  
itens que caibam dentro da mochila (Knapsack  
Problem).  
Solução Baseada em Programação Dinâmica:  
0
[, ] = − 1, ꢇ  
ꢄꢅ ꢁ = 0 ꢈꢉ ꢇ = 0  
ꢄꢅ ꢇ > ꢇ  
max ꢋ + 1, ꢇ − ꢇ , 1, ꢇ  
ꢄꢅ ꢁ > 0 ꢇ  
Exemplo 2: Problema da Mochila  
0
[, ] = − 1, ꢇ  
ꢄꢅ ꢁ = 0 ꢈꢉ ꢇ = 0  
ꢄꢅ ꢇ > ꢇ  
max ꢋ + 1, ꢇ − ꢇ , 1, ꢇ  
ꢄꢅ ꢁ > 0 ꢇ  
Item 1  
V1 = 5  
W1 = 5  
Item 2  
V2 = 4  
W2 = 6  
Item 3  
V2 = 7  
W2 = 8  
Item 4  
V2 = 7  
W2 = 4  
MAX = 13  
w
0
1
2
3
4
5
6
7
8
9
10 11 12 13  
0
1
2
3
4
i
Exemplo 2: Problema da Mochila  
0
[, ] = − 1, ꢇ  
ꢄꢅ ꢁ = 0 ꢈꢉ ꢇ = 0  
ꢄꢅ ꢇ > ꢇ  
max ꢋ + 1, ꢇ − ꢇ , 1, ꢇ  
ꢄꢅ ꢁ > 0 ꢇ  
Item 1  
V1 = 5  
W1 = 5  
Item 2  
V2 = 4  
W2 = 6  
Item 3 Item 4  
V2 = 7 V2 = 7  
MAX = 13  
W2 = 8  
W2 = 4  
w
0
0
0
0
0
0
1
0
0
0
0
0
2
3
0
0
0
0
0
4
0
0
0
0
7
5
6
0
5
5
5
7
7
0
5
5
5
7
8
0
5
5
7
7
9
0
5
5
7
10 11 12 13  
0
1
2
3
4
0
0
0
0
0
0
5
5
5
7
0
5
5
7
0
5
9
9
0
5
9
9
0
5
i
9
12  
12 12 12 14 14  
Exemplo 2: Problema da Mochila  
1
2
3
4
5
6
7
8
9
1
1
1
1
1
1
. Mochila_DP(wi, vi, n, W)  
.
.
.
para w 0 até W faça  
V[0,w] 0  
O(nW)  
para i 1 até n faça  
. V[i,0] 0  
. para i 1 até n faça  
.
para w 0 até W faça  
se wi w então  
.
.
se vi + V[i-1, w-wi] > V[i-1, w] então  
V[i,w] vi + V[i-1, w-wi]  
senão  
0.  
1.  
2.  
V[i,w] V[i-1,w]  
3. senão  
4.  
V[i,w] V[i-1,w]  
5. retorna V[n, W]  
Exemplo 2: Problema da Mochila  
O algoritmo encontra o máximo valor possível que pode ser  
carregado na mochila. Como descobrir quais itens devem ser  
carregados?  
Toda a informação necessária para descobrir quais são os itens está na  
tabela.  
1. i n  
2
3
4
5
6
7
8
9
. k W  
. enquanto i > 0 e k > 0 faça  
. se V[i, k] V[i-1, k] então  
. coloque o item i na mochila  
. ii - 1  
. kk - wi  
. senão  
. i i-1  
Exemplo 2: Problema da Mochila  
1
2
3
4
5
6
7
8
9
. i n  
. k W  
. enquanto i > 0 e k > 0 faça  
. se V[i, k] V[i-1, k] então  
. coloque o item i na mochila  
Item 1  
V1 = 5  
W1 = 5  
Item 2  
V2 = 4  
W2 = 6  
Item 3  
V2 = 7  
W2 = 8  
Item 4  
V2 = 7  
W2 = 4  
.
i i - 1  
MAX = 13  
. k k - wi  
. senão  
.
i i-1  
w
0
0
0
0
0
0
1
0
0
0
0
0
2
0
0
0
0
0
3
0
0
0
0
0
4
0
0
0
0
7
5
0
5
5
5
7
6
0
5
5
5
7
7
0
5
5
5
7
8
0
5
5
7
9
0
5
5
7
10 11 12 13  
0
1
2
3
4
0
5
5
7
0
5
9
9
0
5
9
0
5
9
i
9 12  
7 12 12 12 14 14  
Exemplo 2: Problema da Mochila  
1
2
3
4
5
6
7
8
9
. i n  
. k W  
. enquanto i > 0 e k > 0 faça  
Item 1  
V1 = 5  
W1 = 5  
Item 2  
V2 = 4  
W2 = 6  
Item 3 Item 4  
V2 = 7 V2 = 7  
.
.
se V[i, k] V[i-1, k] então  
W2 = 8  
W2 = 4  
coloque o item i na mochila  
. ii - 1  
. k k - wi  
MAX = 13  
Solução: {Item 3, Item 4}  
9 10 11 12 13  
.
senão  
. i i-1  
w
0
0
0
0
0
0
1
0
0
0
0
0
2
0
0
0
0
0
3
0
0
0
0
0
4
0
0
0
0
7
5
0
5
5
5
7
6
0
5
5
5
7
7
0
5
5
5
7
8
0
5
5
7
7
0
1
2
3
4
0
5
5
7
0
5
5
7
0
5
9
9
0
5
9
9
0
5
i
9
12  
12 12 12 14 14  
Programação Dinâmica  
Outros algoritmos importantes baseados em  
programação dinâmica que veremos ao longo do  
curso:  
Maior Subsequência Comum  
Técnicas de Projeto de Algoritmos  
Infelizmente, não existe uma técnica que seja a  
melhor dentre todas.  
Um problema pode ser resolvido de maneira mais  
eficiente adotando-se uma técnica do que outra.  
Uma técnica pode levar a um algoritmo O(2n) e outra  
2
técnica a um algoritmo O(n ) na resolução de um  
mesmo problema.  
Exercícios  
Lista de Exercícios 05 Programação Dinâmica  
http://www.inf.puc-rio.br/~elima/paa/  
Leitura Complementar  
Levitin. Introduction to the Design and  
Analysis of Algorithms, 3rd Edition, 2011.  
Capítulo 8: Dynamic Programming