Algoritimos

Disponível somente no TrabalhosFeitos
  • Páginas : 16 (3969 palavras )
  • Download(s) : 0
  • Publicado : 18 de outubro de 2011
Ler documento completo
Amostra do texto
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 3Soluçã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.1Conjunto 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15 19 27
27 27 28 29 30 31 31 33 34 35 36 36 37 38 39

C Tabelas com Utilidade Acumulada

39
39 41 42 43

2

1 O Problema da Mochila
O problema da Mochila (knapsack problem ) pode ser enunciado da seguinte forma: Dados um número m ≥ 0, um inteiro positivo n e, para cada iem {1, . . . , n}, um número vi ≥ 0 e um número wi ≥ 0, encontrar um subconjunto S de {1, . . . , n} que maximize v(S) sob a restrição w(S) ≤ m. Onde, v(S) denota a soma i∈S vi e, analogamente, w(S) denota a soma i∈S wi . Os números vi e wi podem ser interpretados como utilidade e peso respectivamente de um objeto i. O número m pode ser interpretado como a capacidade de uma mochila, ou seja, opeso máximo que a mochila comporta. O objetivo do problema é então encontrar uma coleção de objetos, a mais valiosa possível, que respeite a capacidade da mochila. Este problema vem sendo estudado deste o trabalho de D.G. Dantzig[5], devido a sua utilização imediata na Indústria e na Gerencia Financeira, porém foi mais enunciado por razões teóricas, uma vez que este freqüentemente ocorre pelarelaxação de vários problemas de programação inteira. Toda a família de Problemas da Mochila requer que um subconjunto de ítens sejam escolhidos, de tal forma que o somatório das suas utilidades seja maximizado sem exceder a capacidade da mochila. Diferentes tipos de problemas da Mochila ocorrem dependendo da distribuição de ítens e Mochilas como citado em [5]: No problema da Mochila 0/1 (0/1 KnapsackProblem ), cada ítem pode ser escolhido no máximo uma vez, enquanto que no problema da Mochila Limitado (Bounded Knapsack Problem ) temos uma quantidade limitada para cada tipo de ítem. O problema da Mochila com Múltipla Escolha (Multiple-choice Knapsack Problem ) ocorre quando os ítens devem ser escolhidos de classes disjuntas, e se várias Mochilas são preenchidas simultaneamente temos o...
tracking img