Problema da mochila

1 INTRODUÇÃO

Uma pergunta muito frequente nas salas de aula hoje em dia é: “Aonde vou aplicar isso na minha vida?”.
O objetivo deste trabalho é de explicar um algoritmo lógico e mostrar a suas aplicações, além demonstrar toda a sua genialidade.

2 PROBLEMA DA MOCHILA

O problema da mochila (em inglês, Knapsack problem) é um problema de optimização combinatória. O nome dá-se devido ao modelo de uma situação em que é necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo.
O problema da mochila é um dos 21 problemas NP-completos de Richard Karp, exposto em 1972. A formulação do problema é extremamente simples, porém sua solução é mais complexa. Este problema é à base do primeiro algoritmo de chave pública (chaves assimétricas).
Normalmente este problema é resolvido com programação dinâmica, obtendo então a resolução exata do problema, mas também sendo possível usar PSE (procedimento de separação e evolução). Existem também outras técnicas, como usar algoritmo guloso, meta-heurística (algoritmos genéticos) para soluções aproximadas.

3 DEFINIÇÃO

Suponha que tenha uma mochila com capacidade total de e itens distintos. Seja a quantidade de itens que está sendo carregado, cada um com um respectivo peso e valor . Maximizar o valor da mochila nada mais é que maximizar a seguinte equação:

3.1 Problema da Mochila com Repetições (Ilimitado)

Neste caso não existe nenhuma restrição quanta quantidade máxima que se pode carregar do respectivo item. Logo, o problema pode ser visto como a maximização da seguinte equação:

3.2 Problema da Mochila sem Repetições (Limitado)

Nesta situação podemos ver dois problemas envolvidos, sendo eles o problema da mochila limitado 0/1 e o problema da mochila limitado. O segundo caso pode ser visto como uma generalização do primeiro.
Este caso e aplicado na situação onde só e possível pegar