Suponha dado um conjunto de objetos, cada um com um certo peso e um certo valor. Quais dos objetos devo colocar na minha mochila para que o valor total seja o maior possível? Minha mochila tem capacidade para 15 kg apenas.
Esse é um exemplo do problema da mochila (= knapsack problem), também conhecido como problema da mochila booleana, problema booleana da mochila, e problema da mochila zero-um. Trata-se de uma generalização do problema subset sum (mas não deve ser confundido com o problema da mochila fracionária).
Esta página usa a estrutura recursiva do problema
para desenvolver dois algoritmo de força bruta
:
um algoritmo exponencial de enumeração
e um algoritmo de programação dinâmica.
A página foi inspirada na seção 16.2
do CLRS.
Se p[1 .. n] e v[1 .. n] são vetores numéricos e X é um subconjunto do intervalo 1 .. n, denotaremos por p(X) e v(X) as somas ∑i∈X p[i] e ∑i∈X v[i] respectivamente.
Problema da Mochila Booleana: Dados vetores p[1 .. n] e v[1 .. n] de números naturais e um número natural c, encontrar um subconjunto X do intervalo 1 .. n que maximize v(X) sob a restrição p(X) ≤ c.
Em outras palavras, queremos encontrar um subconjunto X do intervalo 1 .. n tal que p(X) ≤ c e v(X) ≥ v(Y) para todo subconjunto Y de 1 .. n tal que p(Y) ≤ c.
Diremos 1, 2, … , n são os objetos do problema, que p[i] é o peso do objeto i, e que v[i] é o valor do objeto i. Diremos que c é a capacidade da instância. Diremos ainda que uma mochila (= knapsack) é qualquer subconjunto X de 1 .. n que satisfaz a restrição p(X) ≤ c. O valor de uma mochila X é o número v(X) . Nosso problema é encontrar uma mochila de valor máximo.
Exemplo A: Considere a instância n = 4, p = (20, 20, 30, 30) e v = (20, 30, 20, 40) do problema da mochila. Represente cada objeto i por um retângulo de altura p[i] e largura v[i].
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.
Um conjunto de objetos assim dispostos é uma mochila
se couber numa faixa de altura igual à capacidade.
O valor da mochila é o comprimento da parte ocupada da faixa.
A figura abaixo representa o conjunto de objetos { 2, 4 }
na faixa pontilhada de altura c = 60.
Esse conjunto é, portanto, uma mochila.
O valor da mochila é 70.
| 2 | |||
| 4 | |||
Exemplo B: Considere a instância do problema da mochila que tem c = 50, n = 5, e p e v dados na tabela abaixo. O conjunto { 2, 3 } é uma mochila de valor máximo. O valor desta mochila é 1000. Os objetos 2 e 3 esgotam a capacidade da instância, mas isso é um acidente, não uma exigência do problema.
| p | 40 | 30 | 20 | 10 | 20 |
| v | 840 | 600 | 400 | 100 | 300 |
| ☑ | ☑ |
Dados vetores p[1 .. n] e v[1 .. n] de números naturais e um número natural c, encontrar um subconjunto X do intervalo 1 .. n tal que v(X) é máximo e p(X) ≤ c.Esta formulação está correta? É ambígua? [Solução]
espaçosuficiente; caso contrário, ignore o objeto. Descreva esta heurística em código. Mostre que a heurística não resolve o problema nem mesmo se os objetos estiverem em ordem decrescente de valor. Mostre que a heurística não resolve o problema nem mesmo quando os objetos estão em ordem crescente de valor específico (valor por unidade de peso). Mostre que a heurística gulosa pode cometer um erro arbitrariamente grande.
rodaro algoritmo?
Tal como o problema subset sum, o problema da mochila booleana tem estrutura recursiva: qualquer solução de uma instância é composta por soluções de suas subinstâncias. Suponha que X é uma solução da instância ( p, v, n, c) do problema. Se n ∉ X então X é solução da subinstância
( p, v, n−1, c)
e se n ∈ X então X − { n } é solução da subinstância
( p, v, n−1, c − p[n]) .
Reciprocamente, se Y é solução da instância ( p, v, n−1, c) e Y′ é solução da instância ( p, v, n−1, c − p[n]) então Y ou Y′ ∪ { n } é solução da instância ( p, v, n, c).
Isso sugere um algoritmo recursivo para o problema
(veja exercício abaixo).
O algoritmo usa força bruta
pois faz uma enumeração (implícita)
de todos os subconjuntos de
1 .. n.
O algoritmo consome Ω(2n)
unidades de tempo
e portanto só é útil
para valores muito pequenos de n.
A exemplo do que fizemos com o problema subset sum, podemos resolver o problema da mochila booleana por programação dinâmica.
A ideia é guardar em uma tabela as soluções das subinstâncias da instância dada. Vamos tratar de todas as subinstâncias que tenham vetor de pesos p[1 .. i] para algum i entre 0 e n e alguma capacidade j entre 0 e c. A tabela de programação dinâmica, que chamaremos t, é então definida assim: para cada i no intervalo 0 .. n e cada j no intervalo 0 .. c,
t[i, j] é o valor de uma solução da instância ( p, v, i, j )
do problema. Em particular, t[0, j] = 0 para todo j e t[i, 0] = 0 para todo i. Graças à estrutura recursiva do problema, a tabela satisfaz a recorrência
| t[i, j] | = | t[i−1, j] | se p[i] > j | |
| max (t[i−1, j], v[i] + t[i−1, j − p[i]]) | se p[i] ≤ j |
para todo i ≥ 1 e todo j ≥ 1. (Observe que todos os números da forma j − p[i] são inteiros não-negativos e portanto a posição [i−1, j − p[i]] da tabela está bem definida.)
A partir dessa recorrência é fácil escrever um algoritmo Mochila-Prog-Din (veja exercício abaixo) para preencher a tabela t e, a partir dela, calcular uma solução X. O consumo de tempo do algoritmo é proporcional ao tamanho da tabela t. Portanto o algoritmo consome
Θ(n c)
unidades de tempo. Como já observamos ao estudar o desempenho da programação dinâmica para o problema subset sum, é melhor dizer que o algoritmo consome Θ( n 2lg c) unidades de tempo para deixar claro que o algoritmo é exponencial.
Exemplo C: Nesse exemplo, o problema da mochila tem n = 4 objetos e capacidade c = 5. Os pesos p e os valores v estão abaixo à esquerda. À direita, temos a tabela t da programação dinâmica. Os números da tabela têm um erro que você deve encontrar.
|
|
9por seu expoente favorito.)
9por seu expoente favorito.)