O problema da mochila booleana também é conhecido como problema booleano da mochila, como problema da mochila zero-um, e simplesmente como problema da mochila. Em inglês, diz-se knapsack problem.
O problema da mochila booleana é uma generalização do problema subset-sum e não deve ser confundido com o problema da mochila fracionária.
Esta página é inspirada na seção 16.2 do CLRS. Veja também a seção 6.1 de KT e o verbete Knapsack problem na Wikipedia e o capítulo 10 do meu Minicurso de Análise de Algoritmos.
Dados números p1,p2,…,pn, v1,v2,…,vn e um subconjunto X de {1,2,…,n}, denotaremos por p(X) e v(X) as somas ∑i∈X pi e ∑i∈X vi respectivamente.
Problema da mochila booleana: Dados números naturais p1, p2, … , pn , v1, v2, … , vn e c, encontrar um subconjunto X de {1,2,…,n} que maximize v(X) sob a restrição p(X) ≤ c.
Diremos 1,2,…,n são os objetos do problema, que pi é o peso e que vi é o valor do objeto i. (A ordem em que os pesos e os valores são dados é, obviamente, irrelevante.) Diremos que c é a capacidade da mochila. Diremos ainda que uma mochila viável é qualquer subconjunto X de {1,2,…,n} tal que p(X) ≤ c. O valor de uma mochila X é o número v(X) . Nosso problema é encontrar uma mochila viável de valor máximo.
Exemplo 1: Tome n = 4, p = (20,20,30,30) e v = (20,30,20,40). Represente cada objeto i por um retângulo de altura pi e largura vi.
1 | 2 | 3 | 4 |
Qualquer conjunto de objetos pode ser disposto "em escada", com o canto inferior direito de um objeto tocando o canto superior esquerdo do objeto seguinte. A figura abaixo representa o conjunto de objetos {2,4}. Esse conjunto é uma solução da instância do problema que tem capacidade c = 60 (altura da faixa cinza).
| 2 | |||
| 4 | |||
Exemplo 2: Tome c = 50, n = 4 e p e v definidos pela figura abaixo. O conjunto {2,4} é uma solução do problema. O valor desta solução é 1000. (A solução do correspondente problema fracionário tem valor 1040.)
| p | 40 | 30 | 20 | 10 |
| v | 840 | 600 | 400 | 100 |
Tal como o problema subset-sum, o problema da mochila booleana tem estrutura recursiva. Suponha que (p1,…,pn, v1,…,vn, c) é uma instância do problema. Seja X uma solução da instância. Temos duas possibilidades: X contém n ou não contém n. No segundo caso, X é solução da subinstância
(p1,…,pn−1, v1,…,vn−1, c)
No primeiro caso, pn ≤ c e X−{n} é solução da subinstância
(p1,…,pn−1, v1,…,vn−1, c−pn).
Essa estrutura recursiva sugere imediatamente um algoritmo para o problema (veja exercício abaixo). Embora isso não seja evidente, o algoritmo faz uma enumeração (implícita) de todos os subconjuntos de {1,…,n} e portanto consome Ω(2n) unidades de tempo no pior caso. O algoritmo só tem valor prático, portanto, para valores muito pequenos de n.
A exemplo do que fizemos com o problema subset-sum, podemos usar a estrutura recursiva para resolver o problema da mochila booleana por programação dinâmica. A ideia é guardar em uma tabela, digamos t, as soluções das (sub)instâncias do problema. A tabela é definida assim: para i = 0,1,…,n e b = 0,1,…,c,
t[i,b]
é o valor de uma solução
da instância
(p1,…,pi,
v1,…,vi,
b)
do problema.
A tabela t satisfaz a seguinte recorrência: para todo i ≥ 1 e todo b,
| t[i,b] | = | t[i−1,b] | se pi > b e | |
| max (t[i−1,b] , t[i−1,b−pi] + vi) | se pi ≤ b . |
(Observe que todos os números da forma b−pi são não negativos e portanto a posição (i−1,b−pi) da tabela está bem definida.)
A partir dessa recorrência é fácil escrever um algoritmo de programação dinâmica (veja exercício abaixo) para preencher a tabela t e, a partir dela, determinar uma solução X. Esse algoritmo consome
Ο(nc)
unidades de tempo, mesmo no pior caso. (A estimativa é justa: o algoritmo consome Ω(nc) unidades de tempo em todos os casos.)
Exemplo 3: Suponha que c = 5 e n = 4. Os vetores p e v são dados pela figura esquerda. A figura direita representa a tabela t. Os números da tabela têm um erro que você deve descobrir.
|
|
O algoritmo de programação dinâmica consome Θ(nc) unidades de tempo mas não pode ser considerado rápido. Para entender essa observação, é preciso compreender a relação entre a expressão nc e o tamanho das instâncias do problema.
Qual o tamanho de uma instância (p1,…,pn, v1,…,vn, c) do problema? É muito razoável dizer que o tamanho dessa instância é 2n+1 (pois a instância consiste em 2n+1 números). Infelizmente, não é possível escrever o produto nc em função de 2n+1. Nossa definição de tamanho deveria levar em conta o valor e não apenas a presença do parâmetro c. Poderíamos adotar o par (2n,c) como tamanho da instância, mas esse definição não é a ideal.
Considere uma questão mais básica: qual a definição mais razoável de tamanho de um número natural, como c por exemplo? Resposta: número de caracteres. Por exemplo, o tamanho do número 2568773 é 7 (e não 2568773). Como c é representado por aproximadamente lg c caracteres, o tamanho de uma instância (p1,…,pn, v1,…,vn, c) do problema é o par
(2n, lg c) .
Como c = 2lg c, podemos dizer que o consumo de tempo do algoritmo Mochila-Prog-Din é
Θ(n 2lg c) .
Portanto, o algoritmo deve ser considerado exponencial.
| Algo (n) |
| 11 o s ← 0 |
| 12 o para i ← 1 até n faça |
| 13 oooo s ← s+i |
|
14
o
devolva s |