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.

Uma tabela com uma linha por item e uma coluna por capacidade, com o caminho de reconstrução a laranja, ao lado de uma mochila e de itens de vários tamanhos
Uma tabela com uma linha por item e uma coluna por capacidade, com o caminho de reconstrução a laranja, ao lado de uma mochila e de itens de vários tamanhos

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.

George Dantzig (à esquerda) recebe a National Medal of Science do presidente Gerald Ford em 1976. Em 1957 Dantzig deu um método ganancioso clássico para o problema da mochila. O próprio nome remonta ao seu pai, Tobias Dantzig.
George Dantzig (à esquerda) recebe a National Medal of Science do presidente Gerald Ford em 1976. Em 1957 Dantzig deu um método ganancioso clássico para o problema da mochila. O próprio nome remonta ao seu pai, Tobias Dantzig.

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