[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 j entre 0 e c,
t[i, j] é o valor de uma solução da instância (p, v, i, j) do problema da mochila booleana.
A segunda parte do algoritmo (linhas 9 a 15) extrai de t o vetor característico x[1 .. n] de uma solução da instância.
| Mochila-Prog-Din (p, v, n, c) |
| 11 . para j := 0 até c |
| 12 .ooo t[0, j] := 0 |
| 13 .ooo para i := 1 até n |
| 14 .oooooo t[i, j] := t[i−1, j] |
| 15 .oooooo se pi ≤ j |
| 16 .ooooooooo t[i, j] := max (t[i, j], vi + t[i−1, j − pi]) |
| 17 . j := c |
| 18 . para i := n decrescendo até 1 |
| 19 .ooo se t[i, j] = t[i−1, j] |
| 10 .oooooo x[i] := 0 |
| 11 .ooo senão x[i] := 1 |
| 12 .ooo senão j := j − pi |
| 13 . 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 Ω(n c).
por linhas
O bloco de linhas 1 a 8 poderia também ser escrito assim:
| 11 . para j := 0 até c |
| 12 .ooo t[0, j] := 0 |
| 13 . para i := 1 até n |
| 14 .ooo para j := 0 até c |
| 15 .oooooo a := t[i−1, j] |
| 16 .oooooo se pi ≤ j |
| 17 .ooooooooo b := vi + t[i−1, j − pi] |
| 18 .oooooo senão b := 0 |
| 19 .oooooo t[i, j] := max (a, b) |
| 11 . para i := 0 até n |
| 12 .ooo t[i, 0] := 0 |
| 13 . para j := 1 até c |
| 14 .ooo t[0, j] := 0 |
| 15 .ooo para i := 1 até n |
| 16 .oooooo a := t[i−1, j] |
| 1⋮ .ooooooo ⋮ |