O algoritmo de programação dinâmica para o problema da mochila booleana (veja a página 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 máximo.
Esta página serve de introdução aos algoritmos de aproximação mencionados na página 1043 do livro CLRS.
Dados números naturais
$p_1, \ldots, p_n$ e $v_1, \ldots, v_n\text{,}$
diremos que $p_i$ é o peso
e $v_i$ é o valor
do objeto $i\text{.}$
Para qualquer subconjunto $X$ de $\conj{1, \ldots, n}\text{,}$
denotaremos por $p(X)$ a soma
$\sum_{i\in X} p_i\,\text{.}$
Dado um número natural $c\text{,}$
diremos que $X$ é uma mochila
(= knapsack)
se $p(X) \leq c\text{.}$
(Em vez de dizer $X$ é uma mochila
,
poderíamos dizer $X$ é viável
.)
O valor de $X$ é o número
$v(X) = \sum_{i\in X} v_i\,\text{.}$
Queremos encontrar uma mochila 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 todas as mochilas. Suporemos então que $1 \leq p_i \leq c$ para todo $i\text{.}$ 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 $p_1, \ldots, p_n\text{,}$ $v_1, \ldots, v_n$ e $c$ tais que $1 \leq p_i \leq c$ para todo $i\text{,}$ encontrar uma mochila de valor máximo, ou seja, um subconjunto $X$ de $\conj{1, \ldots, n}$ que maximize $v(X)$ sob a restrição $p(X) \leq c\text{.}$
Discutiremos a seguir um algoritmo de aproximação
para o problema.
O algoritmo produz uma
mochila que pode não ter valor máximo,
mas tem valor pelo menos metade do 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 $v_i/p_i\,\text{.}$ Para simplificar a descrição do algoritmo, suporemos que os objetos são dados em ordem decrescente de valor específico: \begin{equation}\label{value-per-weight} \frac{v_1}{p_1} \ \geq \ \frac{v_2}{p_2} \ \geq \ \dots \ \geq \ \frac{v_n}{p_n}\,. \end{equation}
O algoritmo recebe uma instância do problema que satisfaz \eqref{value-per-weight} e devolve uma mochila $X$ tal que \[\textstyle v(X) \ \geq \ \frac{1}{2}\,v(M) \] para qualquer mochila $M\text{.}$ A desigualdade vale, em particular, se $M$ for uma mochila de valor máximo.
| Mochila-Quase-Ótima$\,(p, \ v, \ n, \ c)$ |
| 1 . $s := 0$ |
| 2 . $k := 1$ |
| 3 . enquanto $k \leq n$ e $s + p_k \leq c$ |
| 4 .ooo $s := s + p_k$ |
| 5 .ooo $k := k+1$ |
| 6 . $X := \conj{1,2, \ldots, k-1}$ |
| 7 . se $k > n$ ou $v(X) \geq v_k$ |
| 8 .ooo devolva $X$ |
| 9 . senão devolva $\conj{k}$ |
O bloco de linhas 3 a 5 não faz mais que encontrar o maior $k$ tal que $p_1 + \cdots + p_{k-1} \leq c\text{.}$
O algoritmo está correto. No início da linha 7 de Mochila-Quase-Ótima, é claro que $X$ é uma mochila, ou seja, que $p(X) \leq c\text{.}$ Se $k > n$ então $X$ é o conjunto de todos os $n$ objetos e portanto $X$ é uma (a única) mochila de valor máximo. Assim, a desigualdade $v(X) \geq \frac{1}{2} v(M)$ vale trivialmente.
Suponha agora que $k \leq n$ no início da linha 7. De acordo com o enunciado do problema, $p_i \leq c$ para todo $i\text{.}$ Portanto, o conjunto $\conj{k}$ é uma mochila. O algoritmo devolve a mais valiosa das duas mochilas, $X$ e $\conj{k}\text{.}$ Resta provar que \[\textstyle \max\,(v(X), v_k) \ \geq \ \frac{1}{2}\,v(M) \] para qualquer mochila $M\text{.}$ O primeiro passo da prova consiste na seguinte observação: \[\textstyle \max\,(v(X), v_k) \ \geq \ \frac{1}{2}\,(v(X) + v_k)\,. \] Podemos resumir isso dizendo que $\max\,(v(X), v_k) \geq \frac{1}{2}\,v(Y)\text{,}$ onde \[ Y := X \cup \conj{k}\text{.} \] O segundo passo da prova mostra que $v(Y) > v(M)$ qualquer que seja a mochila $M\text{:}$ \begin{align*} v(Y) - v(M) & \ = \ v(Y{-}M) \ - \ v(M{-}Y) \\ & \ = \ \textstyle \sum_{i\in Y-M} v_i \ - \ \sum_{i\in M-Y} v_i \\ & \ = \ \textstyle \sum_{i\in Y-M} \frac{v_i}{p_i}p_i \ - \ \sum_{i\in M-Y} \frac{v_i}{p_i}p_i \\ & \ \geq \ \textstyle \frac{v_k}{p_k} \sum_{i\in Y-M} p_i \ - \ \frac{v_k}{p_k} \sum_{i\in M-Y} p_i \\ %% & \ = \ \textstyle \frac{v_k}{p_k}\,p(Y{-}M) \ - \ \frac{v_k}{p_k}\,p(M{-}Y) \\ & \ = \ \textstyle \frac{v_k}{p_k}\big(p(Y{-}M) \ - \ p(M{-}Y)\big) \\ & \ = \ \textstyle \frac{v_k}{p_k}\big(p(Y) \ - \ p(M)\big) \\ & \ > \ \textstyle \frac{v_k}{p_k}\left(c \ - \ c\right) \\ & \ = \ 0\,. \end{align*}
A passagem da terceira para a quarta linha vale porque $\frac{v_i}{p_i} \geq \frac{v_k}{p_k}$ para todo $i$ em $Y$ e $\frac{v_i}{p_i} \leq \frac{v_k}{p_k}$ para todo $i$ no complemento de $Y\text{.}$ Já a passagem da sexta para a sétima linha vale porque $p(Y) > c$ e $p(M) \leq c\text{.}$
Se juntarmos os dois passos da prova, veremos que $\max\,(v(X), v_k) \geq \mbox{}$ $\frac{1}{2}(v(X) + v_k) = \mbox{}$ $\frac{1}{2} Y > \frac{1}{2} M\text{,}$ como desejado.
Desempenho. Adote $n$ como medida do tamanho da instância $(p, v, n, c)$ do problema. (Poderia igualmente bem ter adotado $2n+2$ como medida do tamanho.) Uma execução de qualquer das linhas do algoritmo consome uma quantidade de tempo que não depende de $n\text{.}$ 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 \eqref{value-per-weight} pode ser feito em tempo $\Theta(n \lg n)\text{.}$ Portanto, o consumo de tempo do processo todo é \[ \Theta(n \lg n)\,. \]
Imagine 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 (= approximation algorithm). Por exemplo, o algoritmo Mochila-Quase-Ótima, junto com o pré-processamento, é linearítmico e produz um resultado de valor pelo menos 50% do ótimo. Esse fator de aproximação pode parecer pouco satisfatório, 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 maior que 50%. O algoritmo de Ibarra e Kim (veja o livro Uma Introdução Sucinta a Algoritmos Aproximação, 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 do algoritmo Mochila-Prog-Din em que os papéis de $p$ e $v$ são trocados.