Problema da mochila
Origem: Wikipédia, a enciclopédia livre.
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 é a 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.
[editar] Definição
Podemos definir o problema matematicamente da seguinte forma:
Dados vetores x[1..n] e w[1..n], vamos denotar por x·w o produto escalar de x por w:
x·w = x[1]w[1] + … + x[n]w[n] .
Suponha dado um número positivo ou nulo W e vetores w[1..n] e v[1..n] com componentes positivos ou nulos. Uma mochila é qualquer vetor x[1..n] tal que
x·w ≤ W e 0 ≤ x[i] ≤ 1 para todo i
O valor de uma mochila é o número x·v. Uma mochila é ótima se tem valor máximo. Consideremos então os dois problemas a seguir:
Problema Fracionário da Mochila (para solução aproximada):
Dados w, v, n e W, encontrar uma mochila ótima.
Problema Booleano da Mochila (para solução exata):
Dados w, v, n e W, encontrar uma mochila ótima dentre as que satisfazem a seguinte restrição adicional: para cada i, x[i] = 0 ou x[i] = 1.
[editar] Referências
[1] http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/mochila.html
[2] http://en.wikipedia.org/wiki/Knapsack_problem
[3] http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_sac_%C3%A0_dos
