Problema da mochila

Problema da mochila: Como maximizar o valor com um peso máximo?

Problema da Mochila acima resolvido no Processing.

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.

História

Também conhecido como "knapsack problem", o Problema da Mochila está relacionado com um grande número de outros modelos de programação. Sua importância está associada exatamente a esse fato.

Foi possivelmente reportado pela primeira vez na literatura por Dantzig (1957) e constitui um marco das técnicas de programação inteira, otimização combinatória e programação dinâmica.

Metaforicamente podemos entendê-lo como o desafio de encher uma mochila sem ultrapassar um determinado limite de peso, otimizando o valor do produto carregado.

O problema da mochila possui alguns variantes que são:

• O Problema simples da mochila: Onde o ladrão possui uma mochila e vários objetos cada tipo com o seu valor.
• O Problema múltiplo da mochila: Onde o ladrão possui mais de uma mochila ou uma mochila com vários bolsos e vários objetos de cada tipo com o seu valor.

O problema simples da mochila foi resolvido por Ronald Rivest, Adi Shamir e Len Adleman em 1982 e o problema dinâmico da mochila foi resolvido por Ernmie Brickell em 1984.

Definição

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

$\sum _{i=1}^{n}v_{i}x_{i}{\mbox{ , sujeito a }}\sum _{i=1}^{n}w_{i}x_{i}\leq W.$

Problema da Mochila com Repetições (Ilimitado)

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

$\textstyle \sum _{i=1}^{n}v_{i}x_{i}{\mbox{ , sujeito a }}\sum _{i=1}^{n}w_{i}x_{i}\leq W{\mbox{ onde }}x_{i}\in \mathbb {N} .$

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.

0/1

Este caso é aplicado na situação onde só é possível pegar uma única unidade de cada item. Portanto temos a restrição de que $x_{i}\in \{0,1\}.$ A equação a ser maximizada pode ser escrita como:

$\sum _{i=1}^{n}v_{i}x_{i}{\mbox{ , sujeito a }}\sum _{i=1}^{n}w_{i}x_{i}\leq W{\mbox{ onde }}x_{i}\in \{0,1\}.$

Ilimitado

Este caso é aplicado na situação onde é possível pegar mais de uma unidade de cada item. Portanto temos a restrição de que $x_{i}$ $\in \{1,2,...,c_{i}\}.$ A equação a ser maximizada pode ser escrita como:

$\sum _{i=1}^{n}v_{i}x_{i}{\mbox{ , sujeito a }}\sum _{i=1}^{n}w_{i}x_{i}\leq W{\mbox{ onde }}x_{i}\in \ \{0,1,...,c_{i}\}.$

Motivação

Imagine que você possui um contentor de certo tamanho e vários produtos com seus valores para serem colocados dentro dele. Porém os produtos devem ser colocados de um jeito que o contentor tenha o maior valor.

Suponha que você tenha em sua máquina uma pasta cheia de arquivos e deseja gravá-los em CD, só que você já sabe de antemão que não vai caber tudo num CD só. Podem ser dois, três... dez CDs. Como proceder para encaixar o máximo de arquivos em cada CD desperdiçando o mínimo espaço em cada disco?

Desses exemplos podemos entender que a motivação do problema da mochila é colocar dentro de um compartimento uma quantidade de objetos com determinadas importâncias para que esse compartimento tenha a maior importância possível.

Aplicações Práticas

O modelo em si pode ser aplicado, além dos exemplos citados acima, em casos como: Investimento de capital, corte e empacotamento, carregamento de veículos, orçamento.

Foi também utilizado para a construção do algoritmo de Criptografia de chave pública, onde no contexto do problema da mochila a chave pública seria o peso total que a mochila pode carregar e a partir daí, por essa palavra a encriptação é gerada.

Resoluções

Por ser um problema combinatório é possível resolvê-lo por enumeração exaustiva, ou seja tentar todas as soluções possíveis e comparando-as para identificar a melhor solução. Porém, isso se torna completamente inviável pois, mesmo em pequenas dimensões como um problema com apenas 20 itens, haveria um número enorme de respostas. Em um problema com mais de 80 itens, o algoritmo levaria bilhões de anos para ser concluído. Assim, o método de resolução por enumeração exaustiva é de utilidade muito reduzida, senão mesmo nula, para problemas de grande dimensão.

Descreveremos aqui três soluções para este algoritmo:

Solução usando Programação Dinâmica

Programação Dinâmica, ou Função Recursiva, foi a primeira técnica mais inteligente que foi usada para resolver esse problema, na década de 50. É um método aprimorado de usar recursividade que ao invés de chamar uma função várias vezes ele, na primeira vez que é chamado, armazena o resultado para que cada vez que a função for chamada novamente volte o resultado e não uma requisição para ser resolvida.

No Método Guloso, uma solução ótima é definida por uma sequência de decisões ótimas locais. Quando esse método não funciona, uma possível saída seria gerar todas as possíveis sequências de decisões e escolher a melhor sequência, como no Backtracking. Porém essa solução é ineficiente, por ser de ordem exponencial. Na programação dinâmica é possível avaliar todas as soluções, garantido assim que a resposta final estará correta, e armazenar resultados anteriores impedindo dessa forma contas repetidas, o que deixa esse algoritmo mais eficiente.

Ilimitado

Para a versão que permite repetições, é preciso pensar nos subproblemas que existem. Pode-se pensar que é possível olhar para mochilas com capacidade menores de forma que $w\leq W.$ Com esta restrição, pode-se escrever:

$K(w)=$ maior valor alcançado com uma mochila de capacidade $w.$

É possível ver isto em forma de subproblemas menores? Se a solução para $K(w)$ inclui o item $i,$ então removendo este item da mochila teremos uma solução ótima para $K(w-w_{i}).$ Em outras palavras, $K(w)$ é simplesmente $K(w-w_{i})+v_{i},$ para algum $i.$ Como não sabemos quem é o $i,$ temos de tentar todas as possibilidades.

$K(w)=\max _{i:w_{i}\leq w}\{K(w-w_{i})+v_{i}\},$

Para resolver, podemos apresentar o seguinte pseudocódigo:

   $K(0)=0$
   ${\mbox{para }}w=1{\mbox{ até }}W{\mbox{ : }}$
       $K(w)=\max\{K(w-w_{i})+v_{i}:w_{i}\leq w\}$
   retornar $K(W)$

Este algoritmo preenche uma tabela unidimensional de tamanho W+1, da esquerda para a direita. Como cada chamada leva um tempo fixo de $O(n),$ e temos que fazer $W$ chamadas, o tempo total de execução será de $O(nW).$

Limitado 0/1

Para o caso limitado, saber ver subproblemas como no caso ilimitado é completamente inútil. Por exemplo, saber que o valor de $K(w-w_{n})$ é alto não ajuda em nada, pelo fato de que não sabemos se o item $n$ já foi ou não utilizado. Precisamos antes refinar o conceito de subproblemas para carregar informação acerca dos itens que já foram utilizados. Para isto, basta adicionar um segundo parâmetro, $0\leq j\leq n:$

$K(w,j)$ = maior valor alcançado com uma mochila de capacidade $w$ e itens $1,...,j.$

A resposta que procuramos é $K(W,n).$ Como é possível expressar um subproblema $K(w,j)$ em termos de subproblemas menores? Simples. Ou o item $j$ é necessário para alcançar o valor ótimo, ou não é:

$K(w,j)=\max\{K(w-w_{j},j-1)+v_{j},K(w,j-1)\}.$

O algoritmo consiste em preencher uma tabela bidimensional, com $W+1$ linhas e $n+1$ colunas. Apesar da tabela agora ser muito maior que no caso ilimitado, o tempo de execução será o mesmo, pois cada chamada leva um tempo fixo de $O(n)$ e $W$ chamadas são feitas, então o tempo total será de $O(nW).$

   Inicializar $K(0,j)=0$ $\forall j=\{1,..,n\}$ e $K(w,0)=0$ $\forall w=\{1,..,W\}$
   para j = 1 até n:
       para w = 1 até W:
           se $w_{j}>w$: $K(w,j)=K(w,j-1)$
           senão: $K(w,j)=\max\{K(w,j-1),K(w-w_{j},j-1)+v_{j}\}$
   retornar $K(W,n)$

Solução usando Backtracking

Backtracking é um algoritmo refinado da busca por força bruta (ou enumeração exaustiva), no qual boa parte das soluções podem ser eliminadas sem serem explicitamente examinadas. É uma estratégia que se aplica em problemas cuja solução pode ser definida a partir de uma sequência de n decisões, que podem ser modeladas por uma árvore que representa todas as possíveis sequências de decisão. De fato, se existir mais de uma disponível para cada uma das n decisões, a busca exaustiva da árvore é exponencial. A eficiência desta estratégia depende da possibilidade de limitar a busca, ou seja, podar a árvore, eliminando os ramos que não levam a solução desejada.

Para tanto é necessário definir um espaço de solução para o problema. Este espaço de solução deve incluir pelo menos uma solução ótima para o problema. Depois é preciso organizar o espaço de solução de forma que seja facilmente pesquisado. A organização típica é uma árvore. Só então se pode realizar a busca em profundidade.

Para o problema da mochila o algoritmo de força bruta compara todas as possibilidades de preenchimento da mochila que não ultrapassem o peso máximo estipulado. Durante este teste, o algoritmo guarda em uma variável a maior utilidade conseguida e ao final de todas as comparações, o resultado do algoritmo está armazenado nesta variável.

Solução usando o Método Guloso

O Método Guloso é um dos algoritmos mais simples que pode ser aplicado a uma grande variedade de problemas, que na maioria possuem n entradas e é necessário obter um subconjunto que satisfaça alguma restrição, como no Problema da Mochila. Qualquer subconjunto que satisfaça esta restrição é chamado de solução viável. Então o que queremos é uma solução viável que maximize ou minimize uma dada função objetivo. Essa função viável que satisfaz a função objetivo é chamada de Solução Ótima.

No Método Guloso construímos um algoritmo que trabalha em estágios, considerando uma entrada por vez. Em cada estágio é tomada uma decisão considerando se uma entrada particular é uma solução ótima. Isto é feito considerando as entradas em uma ordem determinada por um processo de seleção, que é baseado em alguma medida de otimização que pode ou não ser a função objetivo. Na maioria das vezes, porém, essas medidas de otimização resultarão em algoritmos que gerarão soluções sub-ótimas.

Solução usando Algoritmo de Aproximação Gulosa

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.

Um algoritmo que utiliza o método de aproximação tem por objetivo encontrar uma solução aproximada para o problema com tempo na ordem de $n$ e $n^{2}.$ Além disso, temos uma taxa de aproximação representada por:

MAX(C* /C,C/C*)

Onde C* é o custo obtido. Esta taxa de aproximação deve ser menor ou igual a 2.

Para resolução do problema da mochila, utiliza-se o método de aproximação baseado em algoritmo gulosos. Este algoritmo ordena a entrada com relação à taxa obtida da divisão do valor pelo peso, essa ordenação é feita do maior para o menor. O método de ordenação utilizado é o Quicksort o qual possui um tempo de ordenação de $nlog(n).$

Depois de realizada a ordenação, a solução do problema é obtida simplesmente pegando os primeiros elementos da ordenação até que a capacidade da mochila seja atingida, se existir um elemento que ao ser colocado na mochila ultrapasse a sua capacidade, este elemento é desprezado e passa-se para o próximo.

Ligações externas

• Knapsack Problem- implementações em diversas linguagens de programação, no Rosetta Code
• «O problema da mochila booleana» 
• «Knapsack Problem» 
• (PDF) http://homepages.dcc.ufmg.br/~nivio/cursos/pa04/tp2/tp22/tp22.pdf 
• (PDF) http://www.ime.usp.br/~regis/Publications/wscad2002.pdf 
• http://acm.uva.es/archive/nuevoportal/data/problem.php?p=2172 
• http://oglobo.globo.com/blogs/cat/default.asp?a=5&periodo=200403 
• (PDF) http://www.e-bee.com.br/site/wp-content/uploads/2010/11/Problema-da-mochila.pdf 
• (PDF) http://www2.ic.uff.br/~jsilva/artigo_problema_da_mochila.pdf 

Ver também

• Problema de Roteamento de Veículos
• Problema do caixeiro viajante