O problema da mochila booleana

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.

O problema

Dados números p1,p2,…,pnv1,v2,…,vn  e  um subconjunto X de {1,2,…,n}, denotaremos por  p(X)  e  v(X)  as somas  ∑iX pi  e  ∑iX 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 pv 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

Exercícios

  1. Mostre que o problema da mochila booleana pode ser formulado assim: encontrar números x1,…,xn  em {0,1}  que maximizem  x1v1 + … + xnvn  sob a restrição  x1p1 + … + xnpn ≤ c.
  2. Mostre que o problema subset-sum é um caso particular (ou seja, uma coleção de instâncias) do problema da mochila booleana.
  3. Suponha dados números naturais p1,…,pnv1,…,vn  e  c.  Digamos que um segmento é qualquer par  (i,k)  tal que  1 ≤ i ≤ k ≤ n  e  pi+…+pk ≤ c.  O valor de um segmento (i,k) é vi+…+vk.  Considere o problema de determinar um segmento de valor máximo.  Esse problema é um caso particular do problema da mochila booleana?
  4. [Heurística gulosa]  Considere a seguinte heurística para o problema da mochila booleana:  para i = 1, 2, … , n, coloque o objeto i na mochila se houver espaço suficiente; caso contrário, ignore o objeto.  Descreva esta heurística em pseudocódigo.
  5. Mostre que a heurística gulosa não resolve o problema da mochila booleana.  Mostre que a heurística gulosa pode cometer um erro arbitrariamente grande.
  6. Mostre que a heurística gulosa não resolve o problema da mochila booleana nem mesmo quando os objetos estão em ordem crescente de valor específico. (Esta estratégia funciona no caso do problema da mochila fracionária.)
  7. Mostre que o problema do pen drive é um caso particular do problema da mochila booleana.  Mostre que um algoritmo guloso apropriado resolve o problema. 

A estrutura recursiva do problema

Tal como o problema subset-sum, o problema da mochila booleana tem estrutura recursiva.  Suponha que (p1,…,pn, v1,…,vnc) é 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, cpn).

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.

Exercícios

  1. Prove que o problema da mochila booleana de fato tem a estrutura recursiva descrita na seção anterior.
  2. Descreva em pseudocódigo o algoritmo Mochila-Rec que resolve o problema da mochila booleana apoiando-se na estrutura recursiva do problema.  (Basta adaptar o código do correspondente algoritmo para o problema subset-sum.)  Quanto tempo o seu algoritmo consome? Quanto espaço consome?  [Solução]
  3. Mostre que o algoritmo Mochila-Rec (veja exercício anterior) pode vir a recalcular várias vezes a solução de uma mesma instância do problema.  (Sugestão: Suponha que pn = pn−1. Então as instâncias (n−2, cpn) e (n−2, cpn−1) são idênticas.)
  4. Escreva um algoritmo iterativo que resolva o problema da mochila booleana por enumeração explícita. Em cada iteração, o seu algoritmo deve gerar um subconjunto de {1,2,…,n} a partir do anterior.  Depois de gerar um subconjunto, o algoritmo deve calcular o seu peso e valor.
  5. Considere o algoritmo 1.415^n para o problema subset-sum.  Adapte o algoritmo para resolver o problema da mochila booleana.  Quanto tempo o seu algoritmo consome? Quanto espaço consome?

Algoritmo de programação dinâmica

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,bpi] + vi)   se pi ≤ b .

(Observe que todos os números da forma bpi são não negativos e portanto a posição (i−1,bpi) 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.

  1 2 3 4
p 4 2 1 3
v 500 400 300 450
 
  0 1 2 3 4 5
0 303 0 0 0 0 0
1 0 0 0 0 500 500
2 0 0 400 400 500 500
3 0 300 400 400 700 800
4 0 300 400 450 750 850

Exercícios

  1. Descreva em pseudocódigo o algoritmo Mochila-Prog-Din que resolve o problema da mochila booleana por programação dinâmica.  (Basta adaptar o código do correspondente algoritmo para o problema subset-sum.)  Quanto tempo o seu algoritmo consome? Quanto espaço consome?  [Solução]
  2. [CLR 36.1-4, CLRS 34.1-4]  O algoritmo Mochila-Prog-Din é polinomial?

Desempenho da programação dinâmica

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,…,vnc) 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,…,vnc) 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.

Exercícios

  1. O algoritmo abaixo é polinomial? Escreva um algoritmo polinomial que tenha o mesmo efeito.
      Algo (n)
    11 o s ← 0
    12 o para i ← 1 até n faça
    13 oooo ss+i
    14 o devolva s
  2. [Desafio]  Invente um algoritmo que resolva o problema da mochila booleana em tempo Ο(n5).
  3. [Desafio]  Invente um algoritmo que resolva o problema da mochila booleana em tempo Ο(d4), sendo d o número total de dígitos decimais de p1,…,pn, v1,…,vnc.

Valid HTML 4.01 Strict Valid CSS!