Imagine um conjunto de objetos que eu gostaria de colocar na minha mochila. Cada objeto tem um certo peso e um certo valor. Posso escolher uma fração — entre 0% e 100% — de cada objeto para colocar na mochila. (Isso é diferente do que acontece com a mochila booleana.) Minha mochila suporta no máximo 15 kg. Que fração de cada objeto devo colocar na mochila de modo a maximizar o valor total?
Esse é um exemplo do problema da mochila fracionária (= fractional knapsack problem), também conhecido como problema fracionário da mochila e como problema da mochila contínua. O problema é bem mais fácil que o da mochila booleana, podendo ser resolvido com um algoritmo guloso muito rápido.
Esta página foi inspirada na seção 16.2 de CLRS.
Dados vetores x[1 .. n] e p[1 .. n], denotaremos por x · p o produto escalar de x por p. Portanto, x · p = x[1] p[1] + x[2] p[2] + ⋯ + x[n] p[n]. Diremos que um vetor x[1 .. n] é racional se todos seus componentes forem números racionais e natural se todos seus componentes forem números naturais.
Problema da Mochila Fracionária: Dados vetores naturais p[1 .. n] e v[1 .. n] e um número natural c, encontrar um vetor racional x[1 .. n] que maximize x · v sob as restrições x · p ≤ c e 0 ≤ x[i] ≤ 1 para todo i.
Em outras palavras, queremos encontrar um vetor racional x com componentes entre 0 e 1 tal que (1) x · p ≤ c e (2) x · v ≥ y · v para todo vetor racional y com componentes entre 0 e 1 tal que y · p ≤ c.
Diremos 1, 2, … , n são os objetos do problema, que p[1 .. n] é o vetor de pesos, que v[1 .. n] é o vetor de valores, e que c é a capacidade da instância. Diremos que uma mochila fracionária (= fractional knapsack) é qualquer candidato a solução do problema, ou seja, qualquer vetor racional x[1 .. n] tal que x · p ≤ c e 0 ≤ x[i] ≤ 1 para todo i. O valor de uma mochila fracionária x é o número x · v. Nosso problema é encontrar uma mochila fracionária de valor máximo.
Exemplo A: Considere a instância do problema da mochila fracionária que tem n = 5 objetos, capacidade c = 50, e os pesos e valores dados na figura. Na última linha da figura uma mochila fracionária x de valor máximo. O valor dessa solução é x · v = 1040. (O valor da solução do correspondente problema booleano é apenas 1000.)
| p | 40 | 30 | 20 | 10 | 20 |
| v | 840 | 600 | 400 | 100 | 300 |
| x | 1 | 1/3 | 0 | 0 | 0 |
É um pouco surpreendente que um simples algoritmo guloso seja capaz de resolver o problema da mochila fracionária. O critério guloso que o algoritmo implementa dá preferência aos objetos de maior valor específico, isto é, maior valor por unidade de peso. Suporemos então que os objetos foram previamente ordenados de modo que
v[1] / p[1] ≤ v[2] / p[2] ≤ ⋯ ≤ v[n] / p[n]
(sendo v[i] / p[i] infinito quando p[i] = 0). Os objetos são processados em ordem inversa, de n para 1. Veja uma primeira versão do algoritmo:
| Mochila-Fracionária (p, v, n, c) |
| 11 . j := n |
| 12 . enquanto j ≥ 1 e p[j] ≤ c |
| 13 .ooo x[j] := 1 |
| 14 .ooo c := c − p[j] |
| 15 .ooo j := j − 1 z[j] |
| 16 . se j ≥ 1 |
| 17 .ooo x[j] := c / p[j] |
| 18 .ooo para i := j−1 decrescendo até 1 |
| 19 .oooooo x[i] := 0 |
| 10 . devolva x |
Agora veja uma organização mais compacta do código, sempre supondo que os objetos estão em ordem crescente de valor específico, ou seja, que v[1] / p[1] ≤ v[2] / p[2] ≤ ⋯ ≤ v[n] / p[n] :
| Mochila-Fracionária (p, v, n, c) |
| 1 . para j := n decrescendo até 1 |
| 2 .ooo se p[j] ≤ c |
| 3 .oooooo x[j] := 1 |
| 4 .oooooo c := c − p[j] |
| 5 .ooo senão x[j] := c / p[j] |
| 6 .ooo senão c := 0 |
| 7 . devolva x |
Em cada iteração, o algoritmo abocanha o objeto de maior valor específico dentre os objetos disponíveis, sem se preocupar com o que vai acontecer depois. O algoritmo jamais se arrepende do valor que atribuiu a uma componente x[ j] de x. Surpreendentemente, a mochila calculada tem valor máximo.
Exemplo B: Veja mais uma vez o exemlo A, com os obejtos colocados em ordem crescente de valor específico. Para a capacidade c = 50, o algoritmo Mochila-Fracionária produz a solução x que está na última linha.
| p | 10 | 20 | 30 | 20 | 40 |
| v | 100 | 300 | 600 | 400 | 840 |
| v/p | 10 | 15 | 20 | 20 | 21 |
| x | 0 | 0 | 0 | 1/3 | 1 |
Desempenho. Cada execução de cada linha do algoritmo Mochila-Fracionária consome Θ(1) unidades de tempo. Logo, o consumo de tempo total é proporcional ao número de iterações, que é n. Portanto, o algoritmo consome
Θ(n)
unidades de tempo. (Mas isso não inclui o tempo Θ(n log n) de pré-processamento necessário para colocar os objetos em ordem crescente de valor específico.)
Poderíamos medir o consumo de tempo indiretamente, contando o número de comparações de p[j] com c na linha 2 e observando que esse número de comparações é proporcional ao consumo total de tempo.
O algoritmo Mochila-Fracionária está correto? É fácil constatar que o algoritmo produz uma mochila fracionária. É mais difícil provar que a mochila produzida tem valor máximo. A prova decorre da estrutura recursiva do problema. Supondo que v[n] / p[n] ≥ v[i] / p[i] para todo i < n, a estrutura recursiva pode ser formulada assim:
(A primeira propriedade diz que alguma mochila de valor máximo contém a maior fração possível do objeto n.) A prova dessas propriedades é trabalhosa. (Veja exercício abaixo.)
o algoritmo faz isso, depois faz aquilo …, etc.)?