1 Introdução
O problema da mochila é um dos 21 problemas NP-completos de Richard Karp, expostos em 1972. A formulação do problema é extremamente simples, porém sua solução é mais complexa. Este problema é a base do primeiro algoritmo de chave pública (chaves assimétricas).
Normalmente este problema é resolvido com programação dinâmica, buscando 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 Algoritmos Gulosos, meta-heurística (Algoritmos Genéticos) para soluções aproximadas.
Richard Manning Karp é um cientista da computação e teórico computacional da Universidade da California, Berkeley, reconhecido pela sua pesquisa sobre teoria dos algoritmos, pelo qual recebeu um Prêmio Turing em 1985, Medalha Benjamin Franklin em Computação e Ciência Cognitiva em 2004, e o Prêmio Kyoto em 2008.
2 Algoritmos Gulosos
Foi proposto por George Dantzig, em 1957, um algoritmo de aproximação gulosa para resolver o problema da mochila. A versão dele dispõe os itens em ordem decrescente de valor por unidade de peso. Em seguida, começa a inseri-los na mochila com tantas cópias quanto possível do primeiro tipo de item, até que não haja mais espaço na mochila. Caso o problema seja delimitado, ou seja, a oferta para cada tipo de item tenha um limite, o algoritmo pode ficar muito custoso.
3 Variação do Problema da Mochila
3.1 Problema da Mochila Fracionária
Temos 3 queijos, no qual o Queijo 1 tenho um pedaço de 10 kg e consigo vender pelo equivalente a R$ 100,00 reais. Já o queijo 2 tenho um paedaço de 5 kg e posso vender por R$ 80,00 reais. E o queijo 3 tem um pedado de 10 kg e consigo vender por R$ 150,00. Sendo a capacidade máxima da mochila de 20 kg.
Pra esse tipo de problema é possivel fracionar os queijos, ou seja, levar os 20 kilos mais preciosos, que vão trazer maior retorno financeiro. Inicialmente, é necessário calcular o valor por kilo, com isso os queijos custam:
- Queijo 1: 10 reais por kg
- Queijo 2: 16 reais por kg
- Queijo 3: 15 reais por kg
3.2 Problema da Mochila zero-1
3.2.1 Conjuntos
- \(I = itens \ i\)
3.2.2 Parâmetros
- \(P_{i} = peso \ dos \ itens \ i\)
- \(V_{i} = valor \ do \ item \ i\)
- \(W_{i} = capacidade \ da \ mochila\)
3.2.3 Variavel de Decisão
- \(X_{i} = variável \ binária\)
- 1 se o item \(i\) será colocado na mochila;
- 0 caso contrário;
3.2.4 Função Objetivo
\[ MAX \ \sum \sum V_{i}X_{i}\]
3.2.5 Restrições
\[ \sum P_{i}X_{i} \leq \ W_{j}\]
3.2.6 Domínio das Variáveis
\[ X_{i} \in \{0,1\}, \ \forall_{i} \ \in I\]
3.3 Problema da Mochila Multiplas
3.3.1 Conjuntos
- \(I = itens \ i\)
- \(M = mohilas \ j\)
3.3.2 Parâmetros
- \(P_{i} = peso \ dos \ itens \ i\)
- \(V_{i} = valor \ do \ item \ i\)
- \(W_{j} = capacidade \ da \ mochila \ j\)
3.3.3 Variavel de Decisão
- \(X_{ij} = variável \ binária\)
- 1 se o item \(i\) será colocado na mochila;
- 0 caso contrário;
3.3.4 Função Objetivo
\[ MAX \ \sum \sum V_{i}X_{ij}\]
3.3.5 Restrições
Para cada mochila é analizado o limite da capacidade.
\[ \sum P_{i}X_{ij} \leq \ W_{j}, \ \forall \ j \in M\]
Cada Item só pode estar em uma única mochila.
\[ \sum X_{ij} \leq 1, \ \forall i \in \ I, \ \forall j \in M\]
3.3.6 Domínio das Variáveis
\[ X_{ij} \in \{0,1\}, \ \forall_{i} \ \in I\]