[Enunciado] O algoritmo abaixo resolve o problema da mochila booleana. A tabela t tem o seguinte significado: para cada i entre 0 e n e cada b entre 0 e c,
t[i,b] é o valor de uma solução ótima da instância (p1,…,pi, v1,…,vi, b) do problema da mochila booleana.
A segunda parte do algoritmo (linhas 9 a 15) extrai de t uma solução X da instância.
| Mochila-Prog-Din (p, v, n, c) |
| 11 o para b ← 0 até c faça |
| 12 oooo t[0,b] ← 0 |
| 13 oooo para i ← 1 até n faça |
| 14 ooooooo a ← t[i−1,b] |
| 15 ooooooo se pi > b |
| 16 oooooooooo então a′ ← 0 |
| 17 oooooooooo senão a′ ← t[i−1,b−pi] + vi |
| 18 ooooooo t[i,b] ← max(a, a′) |
| 19 o b ← c |
| 10 o X ← { } |
| 11 o para i ← n decrescendo até 1 faça |
| 12 oooo se t[i,b] ≠ t[i−1,b] |
| 13 ooooooo então X ← X ∪ {i} |
| 14 ooooooo então b ← b − pi |
| 15 o devolva X |
(Note que a coluna t[∗,0] não é inicializada com zeros. Ela pode conter elementos não nulos se pi = 0 para algum i.)
É óbvio que o consumo de tempo do algoritmo é Ο(n c) e também Ω(nc). Para colocar em foco o efeito de c sobre o consumo de tempo, faça o seguinte experimento mental. Imagine que os números p1, … , pn e c são multiplicados por 100. O algoritmo consumirá 100 vezes mais tempo para resolver a nova instância, embora essa nova instância seja conceitualmente idêntica à original (pois a multiplicação por 100 é apenas uma mudança de escala).
O bloco de linhas 1 a 8 poderia também ser escrito assim:
| 11 o para b ← 0 até c faça |
| 12 oooo t[0,b] ← 0 |
| 13 o para i ← 1 até n faça |
| 14 oooo para b ← 0 até c faça |
| 15 ooooooo a ← t[i−1,b] |
| 16 ooooooo se pi > b |
| 17 oooooooooo então a′ ← 0 |
| 18 oooooooooo senão a′ ← t[i−1,b−pi] + vi |
| 19 ooooooo t[i,b] ← max(a, a′) |
| 11 o para i ← 0 até n faça |
| 12 oooo t[i,0] ← 0 |
| 13 o para b ← 1 até c faça |
| 14 oooo t[0,b] ← 0 |
| 15 oooo para i ← 1 até n faça |
| 16 ooooooo a ← t[i−1,b] |