O algoritmo de programação dinâmica para o problema da mochila booleana consome muito tempo. Esta página trata de um algoritmo muito mais rápido que pode não encontrar uma mochila de valor máximo mas produz uma mochila cujo valor é pelo menos 50% do ótimo.
Veja a seção 13.2 de BB, a página 1043 do CLRS e a seção 11.8 de KT. Veja também o capítulo 11 do meu Minicurso de Análise de Algoritmos.
Dados números naturais p1,…,pn, v1,…,vn e c diremos que pi é o peso e vi é o valor do objeto i. Para qualquer subconjunto X de {1,…,n}, denotaremos por p(X) a soma ∑i∈X pi e diremos que X é viável se p(X) ≤ c. O valor de X é o número v(X) = ∑i∈X vi.
Queremos encontrar um conjunto viável de valor máximo. É claro que todo objeto de peso maior que c pode ser ignorado. É claro também que todo objeto de peso nulo pode ser incluído em todos os conjuntos viáveis. Suporemos então que 1 ≤ pi ≤ c para todo i. (Esta hipótese não fazia parte de nossa formulação anterior do problema da mochila booleana, mas é importante na presente página.)
Problema da mochila booleana: Dados números naturais p1,…,pn, v1,…,vn e c tais que 1 ≤ pi ≤ c para todo i, encontrar um subconjunto X de {1,…,n} que maximize v(X) sob a restrição p(X) ≤ c.
Em outras palavras, queremos encontrar um conjunto viável de valor máximo. O algoritmo que discutiremos abaixo produz um conjunto viável X que pode não ter valor máximo, mas chega perto no seguinte sentido:
v(X) ≥ ½ v(S)
sendo S um conjunto viável de valor máximo.
Nosso algoritmo tem caráter guloso e dá preferência aos objetos de maior valor específico. (O valor específico de um objeto i é o número vi/pi.) Para simplificar a descrição do algoritmo, suporemos que os objetos são dados em ordem decrescente de valor específico, ou seja, que
| v1/p1 ≥ v2/p2 ≥ … ≥ vn/pn . | (*) |
O algoritmo recebe uma instância do problema que satisfaz (*) e devolve um subconjunto viável X de {1,…,n} tal que v(X) ≥ ½ v(S), sendo S é um subconjunto viável de valor máximo:
| Mochila-Quase-Ótima (p, v, n, c) |
| 1 .o s ← 0 |
| 2 .o k ← 1 |
| 3 .o enquanto k ≤ n e s+pk ≤ c faça |
| 4 .oooo s ← s + pk |
| 5 .oooo k ← k + 1 |
| 6 .o X ← {1, 2, …, k−1} |
| 7 .o se k > n ou v(X) ≥ vk |
| 8 .oooo então devolva X |
| 9 .oooo senão devolva {k} |
O bloco de linhas 3 a 5 não faz mais que encontrar o maior k tal que p1+…+pk−1 ≤ c.
No início da linha 7, é claro que o conjunto X é viável. Se k > n então X = {1,…,n} e portanto v(X) ≥ ½ v(S), como prometido.
Suponha agora que k ≤ n no início da linha 7. Como vi ≤ c para todo i, o conjunto {k} é viável. O algoritmo devolve o mais valioso dentre X e {k}. Resta mostrar que
max (v(X), vk) ≥ ½ v(S)
para todo conjunto viável S. O primeiro passo da demonstração consiste na seguinte observação:
max (v(X), vk) ≥ ½ (v(X) + vk) = ½ v(R) ,
sendo R = X ∪ {k}. O segundo passo mostra que v(R) > v(S) qualquer que seja o conjunto viável S:
| v(R) − v(S) | = | v(R−S) − v(S−R) |
| = | ∑i∈R−S vi − ∑i∈S−R vi | |
| = | ∑i∈R−S (vi/pi) pi − ∑i∈S−R (vi/pi) pi | |
| ≥ | (vk/pk) ∑i∈R−S pi − (vk/pk) ∑i∈S−R pi | |
| = | (vk/pk) p(R−S) − (vk/pk) p(S−R) | |
| = | (vk/pk) (p(R) − p(S)) | |
| > | (vk/pk) (c − c) | |
| = | 0 . |
A passagem da terceira para a quarta linha vale porque vi/pi ≥ vk/pk para todo i em R e vi/pi ≤ vk/pk para todo i no complemento de R. Já a passagem da sexta para a sétima linha vale porque p(R) > c e p(S) ≤ c.
Adote n (poderia igualmente bem ter adotado 2n+1) como medida do tamanho da instância (p, v, n, c) do problema. Uma execução de qualquer das linhas do algoritmo consome uma quantidade de tempo que não depende de n. O bloco de linhas 3-5 é executado no máximo n vezes. Assim, o algoritmo todo consome
unidades de tempo, tanto no pior quanto no melhor caso. O pré-processamento necessário para fazer valer (*) pode ser feito em tempo Θ(n lg n). Portanto, o consumo de tempo do processo todo é
Θ(n lg n) .
Imagina um problema qualquer de maximização, como é o problema da mochila. Um algoritmo rápido cujo resultado é uma fração pré-determinada da solução ótima é conhecido como algoritmo de aproximação. O algoritmo Mochila-Quase-Ótima, por exemplo, produz um resultado de valor pelo menos 50% do ótimo. Esse fator de aproximação pode parecer grosseiro, mas é suficiente para algumas aplicações que precisam de um algoritmo muito rápido.
Outros algoritmos de aproximação para o problema da mochila booleana têm fator de aproximação bem melhor que 50%. O algoritmo de Ibarra e Kim (veja o livro de Cristina Gomes Fernandes e outros, por exemplo) garante um fator de aproximação tão próximo de 100% quanto o usuário desejar. Como seria de se esperar, o consumo de tempo do algoritmo é tanto maior quanto maior o fator de aproximação solicitado. O algoritmo de Ibarra e Kim é baseado numa variante de Mochila-Prog-Din em que os papéis de p e v são trocados.