Estudante

UNIVERSIDADE FEDERAL DE SANTA CATARINA ­ UFSC
CENTRO TECNOLÓGICO – INE

Problema da mochila e uma possível redução

Disciplina: Teoria da Computação

Florianópolis, 2014

1

Sumário
1. Introdução
2. Prova
4. Exemplo de problema de mochila
5. Considerações finais
6. Referências Bibliográficas

2

1. Introdução O problema da mochila se refere à seguinte situação:
Imagine que você tem uma mochila com um espaço “X” e você tem um conjunto “N” de objetos com pesos e valores diferentes entre si. O objetivo do problema é colocar um conjunto certo de objetos “N” tal que o valor total dos objetos dentro da mochila seja o máximo possível. A laura quer que a introdução tenha cinco linhas pelo menos, porquê de outra forma parece que o tema não está explicitado direito. Então está feito. Cinco linhas ela quer, cinco linhas ela teve.

3

2. Prova A partir do enunciado conseguimos notar que para conseguirmos o maior valor para um conjunto de objetos que caibam na mochila, teremos que calcular todas as combinações possíveis dos objetos e então comparar os seus valores. Isso mostra que ele tem um grau de complexidade polinomial. Formalizando:
Vamos imaginar que cada item i tem um peso Wi e um valor Vi. A capacidade da mochila é dado por C.
Supomos também que num caso específico do problema da mochila cada item possa ser pego somente uma vez. Sendo assim quando Xi= 1, significa que ele foi pego e quando Xi= 0 significa que ele não foi pego.
Sendo o valor total de mochila como M: n Maximizar M(x) =

∑

ViXi tal que :

i = 1 n ∑

WiXi ≤ C lembrando que Xi ε {0, 1}.

i =i

Para provar que um problema Π pertence a NP­Completo é necessário provar que:

1.1 O Problema