O problema da mochila fracionária também é conhecida como problema fracionário da mochila e como problema da mochila contínua. Em inglês, o problema é conhecido como fractional knapsack problem. Ele é bem mais fácil que o problema da mochila booleana e pode ser resolvida por um algoritmo guloso muito eficiente.
Esta página é inspirada na seção 16.2 de CLRS. Veja também a seção 6.1 de KT e o verbete Continuous knapsack problem na Wikipedia.
Dados vetores (x1,x2,…,xn) e (p1,p2,…,pn), denotaremos por x · p o produto escalar de x por p. Portanto, x · p = x1p1 + x2p2 + … + xnpn . Diremos que um vetor (x1,x2,…,xn) é racional se todos os seus componentes forem números racionais e natural se todos os seus componentes forem números naturais.
Problema da mochila fracionária: Dados vetores naturais (p1, p2, … , pn), (v1, v2, … , vn) e um número natural c, encontrar um vetor racional (x1, x2, … , xn) que maximize x · v sob as restrições x · p ≤ c e 0 ≤ xi ≤ 1 para todo i.
Diremos que (p1,…,pn) é o vetor de pesos, que (v1,…,vn) é o vetor de valores e que c é a capacidade do problema. Diremos que uma mochila fracionária viável é qualquer vetor racional (x1,…,xn) tal que x · p ≤ c e 0 ≤ xi ≤ 1 para todo i. O valor de uma mochila x é o número x · v. Nosso problema é encontrar uma mochila viável de valor máximo.
Motivação: Imagine que tenho n objetos que eu gostaria de colocar em uma mochila de capacidade c. Cada objeto i tem peso pi e valor vi. Posso escolher uma fração (entre 0% e 100%) de cada objeto para colocar na mochila. Quero fazer isso de modo a respeitar a capacidade da mochila e maximizar o seu valor.
Exemplo: Suponha c = 50 e n = 4. A figura abaixo dá os valores de p e v. Mais abaixo, temos uma solução x do problema da mochila fracionária. O valor dessa solução é x · v = 1040. (A solução do correspondente problema booleano tem valor 1000.)
| p | 40 | 30 | 20 | 10 | 20 |
| v | 840 | 600 | 400 | 100 | 300 |
| x | 1 | 1/3 | 0 | 0 | 0 |
O seguinte algoritmo guloso resolve o problema da mochila fracionária. O algoritmo exige que os dados estejam em ordem crescente de valor específico (ou seja, valor por unidade de peso):
v1/p1 ≤ v2/p2 ≤ … ≤ vn/pn
(se pi=0 então
vi/pi é infinito).
É nesta ordem mágica
que está o segredo do funcionamento do algoritmo.
| Mochila-Fracionária (p, v, n, c) |
| 11 o j ← n |
| 12 o enquanto j ≥ 1 e pj ≤ c faça |
| 13 oooo xj ← 1 |
| 14 oooo c ← c − pj |
| 15 oooo j ← j − 1 |
| 16 o se j ≥ 1 então |
| 17 oooo xj ← c/pj |
| 18 oooo para i ← j−1 decrescendo até 1 faça |
| 19 ooooooo xi ← 0 |
| 10 o devolva x |
Eis uma organização mais compacta do código:
| Mochila-Fracionária (p, v, n, c) |
| 1 o para j ← n decrescendo até 1 faça |
| 2 oooo se pj ≤ c |
| 3 ooooooo então xj ← 1 |
| 4 ooooooo então c ← c − pj |
| 5 ooooooo senão xj ← c/pj |
| 6 ooooooo senão c ← 0 |
| 7 o devolva x |
O algoritmo é guloso porque, em cada iteração, abocanha o objeto de maior valor específico dentre os disponíveis, sem se preocupar com o que vai acontecer depois. O algoritmo jamais se arrepende do valor atribuído a um componente de x.
Por que o algoritmo dá a resposta correta? É evidente que o algoritmo produz uma mochila fracionária viável; o difícil é provar que ela é tem valor máximo. A prova se apoia no seguinte par de propriedades:
1. Se vn/pn ≥ vi/pi para todo i então existe uma mochila viável de valor máximo (x1,…,xn) tal que xn = min(1, c/pn).
2. Se (x1,…,xn) é uma mochila viável de valor máximo para a instância dada do problema então (x1,…,xn−1) é uma mochila viável de valor máximo para a instância definida pelos parâmetros n−1 e c − xnpn.
Prove essas propriedades!
É evidente que o consumo de tempo do algoritmo é Ο(n). (Isso não inclui o tempo Θ(n log n) necessário para colocar os objetos em ordem crescente de valor específico.) Em outras palavras, o consumo de tempo é da mesma ordem de grandeza que o tempo gasto com a leitura dos dados. Portanto, o algoritmo é muito rápido.
A estimativa que acabamos de fazer é justa: o algoritmo consome Ω(n) unidades de tempo, mesmo no melhor caso.