O problema da mochila
Uma caminhante com um limite de peso, um ladrão com um saco, uma empresa com um orçamento e uma lista de projetos: todos enfrentam a mesma pergunta. Que coisas devem entrar para obter o maior valor sem ultrapassar o limite? É o problema da mochila, e a programação dinâmica resolve-o de forma exata quando os pesos são números inteiros de tamanho moderado.
O problema
Há n itens, cada um com um peso e um valor, e uma mochila que aguenta no máximo um peso W. Escolha um conjunto de itens cujo peso total seja no máximo W e cujo valor total seja o maior possível. Cada item entra inteiro ou fica de fora, e é por isso que se chama problema da mochila 0/1. Com n itens há 2ⁿ conjuntos possíveis, por isso experimentá-los todos depressa se torna impossível.
A tabela
Seja best[i][w] o maior valor que cabe no peso w usando só os primeiros i itens. Então best[0][w] = 0, e em cada linha seguinte há duas escolhas: deixar o item i de fora, o que dá best[i − 1][w], ou, se o seu peso wᵢ couber, metê-lo na mochila, o que dá o seu valor mais best[i − 1][w − wᵢ]. O maior dos dois é best[i][w]. Ao preencher a tabela linha a linha, as duas células necessárias estão sempre prontas.
Um exemplo
Considere uma capacidade de 7 e quatro itens com pesos 1, 3, 4 e 5 e valores 1, 4, 5 e 7. Só com o primeiro item, cada capacidade a partir de 1 vale 1. Ao acrescentar o segundo, a capacidade 4 pode levar ambos por 5. Ao acrescentar o terceiro, a capacidade 7 pode levar os itens 2 e 3 por 9. O quarto item, de peso 5 e valor 7, podia juntar-se ao item 1 por 8 com capacidade 6 ou 7, mas 9 é melhor, por isso a célula do canto inferior direito é 9: leve os itens de peso 3 e 4.
Quão difícil é?
A tabela precisa de cerca de n·W passos. Parece rápido, mas W é um número, e um número com d algarismos pode chegar a 10 elevado a d, por isso o trabalho cresce exponencialmente com o tamanho da entrada. O problema da mochila é NP-difícil; foi um dos 21 problemas NP-completos de Richard Karp, de 1972. Na prática, a tabela, o método branch and bound e bons esquemas de aproximação resolvem bem grandes casos reais.
História e aplicações
O nome remonta ao matemático Tobias Dantzig, no início do século XX, e o seu filho George Dantzig apresentou um método guloso clássico para o problema em 1957. Os problemas da mochila surgem na elaboração de orçamentos e na seleção de carteiras de investimento, no corte de matéria-prima com o mínimo de desperdício, no carregamento de mercadorias e até nos primórdios da criptografia de chave pública: o criptossistema de Merkle–Hellman, de 1978, assentava num problema da mochila e foi quebrado poucos anos depois.
Explore
Abra a aplicação, mude para a vista Tabela e prima Avançar. A célula laranja está a ser preenchida, e as células azuis são as duas que ela compara: a célula logo acima e, na linha de cima, a célula que está tantas colunas à esquerda quanto o peso do item. Depois da última célula, a reconstrução sobe a laranja a partir do canto inferior direito, e os itens na mochila aparecem por baixo da tabela.
Perguntas frequentes
Qual é a diferença entre a mochila 0/1, limitada e ilimitada?
Na versão 0/1, cada item é levado no máximo uma vez. Na versão limitada, cada item tem um número limitado de cópias, e na ilimitada um número qualquer. A tabela muda muito pouco entre elas.
O método guloso alguma vez acerta na mochila?
No problema da mochila fracionária, em que os itens podem ser divididos, levar primeiro o melhor valor por peso é ótimo. Com itens inteiros pode ficar muito longe, embora a melhor opção entre o método guloso e o item mais valioso sozinho valha sempre pelo menos metade do melhor valor.
De quanta memória precisa a tabela?
(n + 1)·(W + 1) células para a tabela completa, que é o necessário para reconstruir os itens. Se só se quiser o melhor valor, basta uma linha de W + 1 células, preenchida da direita para a esquerda.
A mochila é o mesmo que a soma de subconjuntos?
A soma de subconjuntos é o caso particular em que o valor de cada item é igual ao seu peso e a pergunta é se a mochila pode ser enchida exatamente. Também é NP-completo e resolve-se com o mesmo tipo de tabela.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Experimentar o problema da mochila