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