O problema da mochila fracionária

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.

O problema

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 pv. 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

Algoritmo guloso

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 jn
12 o enquanto  j ≥ 1  e  pjc  faça
13 oooo xj ← 1
14 oooo ccpj
15 oooo jj − 1
16 o se  j ≥ 1  então
17 oooo xjc/pj
18 oooo para  ij−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)
o para  jn  decrescendo até  1  faça
oooo se  pjc
ooooooo então  xj ← 1
ooooooo então  ccpj
ooooooo senão  xjc/pj
ooooooo senão  c ← 0
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/pnvi/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!

Exercícios

  1. [CLRS 16.2-1]   Prove que o algoritmo guloso discutido acima produz uma mochila fracionária viável de valor máximo.
  2. Escreva uma versão simplificada do algoritmo Mochila-Fracionária que só devolve o valor de uma mochila fracionária viável de valor máximo (não devolve x).  Escreva duas versões: uma recursiva e uma iterativa.

Desempenho do algoritmo guloso

É 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.

Valid HTML 4.01 Strict Valid CSS!