evaluacion 2 paa 2017 1

Prévia do material em texto

Universidade Federal do Amazonas 
Instituto de Computação 
Programa de Pós-Graduação em Informática 
Projeto e Análise de Algoritmos – 2017/01 
2a. Exercício Avaliativo Não-Programado 04/05/2017 
 
Aluno: ____________________________________________________ 
 
Questão 1. Problema de Mochila Fracionária. Imagine que temos n objetos que 
gostaríamos de colocar em uma mochila de capacidade c. Cada objeto i tem peso pi 
e valor vi. Podemos escolher uma fração (entre 0% e 100%) de cada objeto para 
colocar na mochila. Queremos fazer isso de modo a respeitar a capacidade da 
mochila e maximizar o seu valor. Exemplo: suponha c = 50 e n = 4. A figura abaixo 
dá os valores de p e v. Mais abaixo, temos uma solução x do problema da mochila 
fracionária. O valor dessa solução é x· v = 1040. 
	
p 40 30 20 10 20 
v 840 600 400 100 300 
x 1 1/3 0 0 0 
	
Pede-se: apresente um algoritmo guloso para resolver o problema da Mochila 
Fracionária. 
 
Questão 2. Problema da Seleção de Atividades: Dado um conjunto de atividades, 
definidas por seus tempos de início e fim, alocar o maior número possível de 
atividades em um período de tempo definido. Por exemplo, um conjunto de 
palestras que devem ser alocadas em um auditório. 
 
 Atividades 
 A B C D E F G H I J K 
Início 
Fim 
4 
8 
6 
7 
13 
14 
4 
5 
2 
4 
6 
9 
7 
10 
9 
11 
1 
6 
3 
13 
9 
12 
 
Solução: E[2,4]; B[6,7]; H[9,11]; C[13,14] 
 
Apresente um algoritmo guloso para solucionar este problema.