Exercício 1
A) Caminho 3 – 4 -3
B) Caminho
100 – 1 – 1 – 100
C) OPT(i) solução ótima considerando os i primeiros nós
OPT(i) = 0, se i=0
OPT(i) = w(i), se i=1
OPT(i) = max{ w(i)+OPT(i-2), OPT(i-1) }, se i>1
Exercício 2
B)
OPT(j) = max { h(j), l(j)}, se j=1
OPT(j) = max { h(j)+OPT(j-2), l(j)+OPT(j-1) }, se j > 1
Tamannho da Tabela é O(n) e cada chamada gasta O(1) 
complexidade O(n)
Exercício 3
A) Arestas 1-2 , 1-3, 3-4, 3-5, 2-5.
Algoritmo computa 1-2-5 e o ótimo é 1-3-4-5
B) OPT(i), caminho mais longo até n partindo de i
OPT (i )  1  max {OPT ( j )}, para i  n
i  j e ( i , j )E
OPT (n)  0
Complexidade O(m+n)
Exercício 5
q(i,j): como a qualidade da string que começa na posição i e termina na j
OPT(j) é o valor da solução ótima para o prefixo que termina na posição j
OPT ( j )  max{q(i, j )  OPT (i  1)}, se j  0
i j
OPT ( j )  0, caso contrário
Tamanho da Tabela é O(n) e cada chamada gasta O(n)  complexidade O(n2)
Exercício 6
f(i,j): quadrado da folga de uma linha que contem as palavras w(i),..,w(j).
j


 L  ( j  i )   ci 
k i


2
OPT(j): solução ótima considerando as j primeiras palavras
OPT ( j )  max{ f (i, j )  OPT (i  1)}, se j  0
i j
OPT ( j )  0, caso contrário
Tamanho da Tabela é O(n) e cada chamada gasta O(n2)  complexidade O(n3)
Pode ser melhorado para O(n2) se a tabela f(i,j) for preprocessada
Exercício 7
MIN (j): valor mínimo da ação nos j primeiros dias
OPT(j) é o lucro máximo que pode ser obtido considerando os j priemrios dias
OPT(j)= max { p(j)-Min(j-1), OPT(j-1) }, se j>0
OPT(j)=0 , caso contrário
MIN( j ) = min { p(j) , MIN(j-1) }
Tamanho da Tabela é O(n) e cada chamada gasta O(1)  complexidade O(n)
Exercício 9
OPT(j): Número máximo de terabytes que podem ser processados até o dia j
 j

OPT( j )  max  min{sk i , xk }  OPT(i  1), se j  0
i j
k i 1

OPT( j )  0, caso contrário
Tamanho da Tabela é O(n) e cada chamada gasta O(n)  complexidade O(n2)
Exercício 20
OPT(i,h): Maior soma de notas possível considerando somente os i primeiros
projetos e h horas disponíveis
OPT (i, h)  max f i (t )  OPT (i  1, h  t ), se j  0
t h
OPT ( j )  0, caso contrário
Tamanho da Tabela é O(Hn) e cada chamada gasta O(H)  complexidade O(nH2)
Nota. Pode ser melhorado para O(n.g.H)
Exercício 28
a)
É fácil ver que existe uma solução S onde todos os jobs escalonáveis aparecem
antes dos não escalonáveis.
Assuma que j e i são dois jobs consecutivos invertidos dentre os escalonáveis
Trocando j e i mantemos o mesmo número de jobs esconáveis