Algoritimos

PROJETO E ANÁLISE DE ALGORITMOS

Ruiter Braga Caldas Professor - Nivio Ziviani

Sumário
1 O Problema da Mochila
1.1 1.2 1.3 Provar que o Problema da Mochila é NP-Completo . . . . . . . . . . Mostrar que o Problema está em NP . . . . . . . . . . . . . . . . . . Redução Polinomial . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2 2 2

2 Solução usando Backtracking 3 Solução usando Programação Dinâmica 4 Solução usando o Método Guloso 5 Comparação entre os Métodos
5.1

4 6 10 11

Resposta para os Conjuntos de Dados . . . . . . . . . . . . . . . . . . 13

6 Estruturas de Dados A Código Fonte B Tabelas com tempos de execução
B.1 Método Guloso . . . B.1.1 Conjunto I . . B.1.2 Conjunto II . B.1.3 Conjunto III . B.1.4 Conjunto IV . B.2 Método Dinâmico . . B.2.1 Conjunto I . . B.2.2 Conjunto II . B.2.3 Conjunto III . B.2.4 Conjunto IV . B.3 Método Backtracking B.3.1 Conjunto I . . B.3.2 Conjunto II . B.3.3 Conjunto III . B.3.4 Conjunto IV . C.1 C.2 C.3 C.4 Conjunto Conjunto Conjunto Conjunto I I I I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .