Lista de exercicio 9 - Cormen 2º Edição

Prévia do material em texto

Aluno: Vinícius Barcelos Silva 
Matricula: 108251 
Lista 9 
 
16.1­3 
 
Encontre o vetor S1 de atividades compatíveis de S para a primeira sala, de forma que o vetor esteja o 
máximo possível preenchido. 
Encontre o vetor S2 de atividades compatíveis de S ­ S1 para a segunda sala, de forma que o vetor esteja o 
máximo possível preenchido. 
Repita até todas as atividades serem distribuídas 
 
16.1­4 
 
Selecionar {a2}, sendo que a melhor solução seria {a1, a3} 
 
Selecionar {a6} primeiro e depois uma das {a1, a2, a3, a4} e uma das {a8, a9, a10, a11}, sendo que a 
melhor solução seria {a1, a5, a7, a11} 
 
16.2­2 
 
c[i, w] =  0 se i = 0 ou w = 0, 
c[i­1, w] se  > w,wi  
maior(  + c[i ­ 1, w ­  ], c[i­1, w])vi wi se i > 0 e w >= wi  
 
mochila(v, w, n, W) 
{ 
c[0 ... n, 0 ... W] 
 
para w = 0 até W 
c[0, w] = 0 
 
para i = i até n 
c[i, 0] = 0 
 
para w = 1 até W 
se w[i] <= w 
se v[i] + c[i ­ 1, w ­ w[i]] > c[i ­ 1, w] 
c[i, w] = v[i] + c[i ­ 1, w ­ w[i] 
senão c[i, w] = c[i ­ 1, w] 
senão c[i, w] = c[i­1, w] 
} 
 
16.2­3 
 
Supondo que a ordem dos itens é crescente por valor. 
Preencha a mochila o máximo possível com os itens de maior valor, dessa forma a mochila estará com 
muitos itens de valor alto. 
 
16.2­4 
 
A melhor estratégia seguindo o paradigma guloso é, começando com o tanque cheio, seguir até o posto 
mais longe que ele conseguir ir, neste posto reabastecer e prosseguir novamente ao posto mais longe 
possível. Dessa forma ele fará o minimo de paradas possíveis. 
 
16.3­2 
 
 
      Simbolo           Codigo