Lista de exercicio 10 Analise e Projeto de Algoritmos

Aluno: Vinícius Barcelos Silva
Matricula: 108251
Lista 10 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 wi > w, maior( vi + c[i ­ 1, w ­ wi ], c[i­1, w]) 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