programação dinâmica

Prévia do material em texto

6. Programac¸a˜o Dinaˆmica
1. O comando diff aplicado a dois arquivos fornece as modificac¸o˜es que foram feitas num arquivo
em relac¸a˜o ao outro. Isto e´, as diferenc¸as entre eles. Explique como o comando diff pode ser
obtido em func¸a˜o do problema subsequeˆncia comum mais longa.
2. O problema da mochila 0-1 tem como dados: um conjunto de n itens onde o item i custa ri Reais
e pesa wi gramas, onde ri e wi sa˜o inteiros. Desejamos escolher um conjunto E ⊆ {1, 2, . . . , n} dos
itens tais que
∑
i∈E ri seja ma´ximo mas sujeito a
∑
i∈E wi ≤M , onde M e´ um nu´mero natural,
chamado capacidade da mochila. Para resolver este problema por PD considere a func¸a˜o:
Para resolver o problema da mochila 0-1 por PD considere a func¸a˜o:
A(j, Y ) e´ o valor ma´ximo (em Reais) que pode ser carregado em uma mochila de capacidade Y
so´ utilizando os itens de 1 a j.
Queremos determinar A(n,M).
Observe que A(0, Y ) = 0 e A(j, 0) = 0.
(a) Verifique se a relac¸a˜o de recorreˆncia para A(j, Y ) esta´ correta.
A(j, Y ) = A(j − 1, Y ) se wj > Y
A(j, Y ) = max{A(j − 1, Y ), rj + A(j − 1, Y − wj)} se wj ≤ Y.
(b) Descreva um algoritmo que calcula A indutivamente usando uma tabela.
(c) Qual a complexidade do algoritmo?
3. Dado um conjunto de valores de moedas C = {c1, . . . , cn} e um valor v, queremos saber se e´
poss´ıvel formar o valor v utilizando somente moedas de C e, caso positivo, a menor quantidade
de moedas utilizadas. Assuma que existe uma quantidade suficiente de cada valor de moeda
para formar o valor desejado, se for poss´ıvel.
(a) Deˆ uma soluc¸a˜o em PD.
(b) Relacione o problema das moedas com o problema da mochila.
4. O problema da Maior Subsequeˆncia Crescente consiste em: dado uma sequeˆncia de nu´meros
inteiros distintos X = x1, x2, . . . , xn, queremos determinar o maior m tal que Y = y1, . . . , ym
seja uma subsequeˆncia de X com y1 < y2 < . . . < ym.
Por exemplo, se X = 1, 2, 9, 3, 8, 4, 7, 6, temos que Z = 1, 3, 7 e´ uma subsequeˆncia crescente de
X e 1, 2, 3, 4, 7 tambe´m e´, mas e´ maior que Z.
(a) Deˆ uma formulac¸a˜o de PD para a soluc¸a˜o deste problema. Qual e´ a complexidade de tempo
e de espac¸o do seu algoritmo?
(b) Observe que e´ poss´ıvel resolver Maior Subsequeˆncia Crescente usando o algoritmo para o
problema da Maior Subsequeˆncia Comum. Explique como e por que esta ideia esta´ correta.
5. ( ? ) O problema da Selec¸a˜o de Atividades com Pesos e´ o mesmo de Selec¸a˜o de Ati-
vidades so´ que a cada atividade esta´ tambe´m associado um valor vi, e deseja-se o conjunto de
atividades compat´ıveis de valor ma´ximo. Deˆ uma soluc¸a˜o em PD para este problema.