Página preparada por Paulo
Feofiloff para a disciplina MAC 338 Análise de
Algoritmos, versão 1999.
O endereço original desta página é http://www.ime.usp.br/~pf/mac338/aulas/mochila.htm.
Esta página é um resumo da discussão que está no capítulo 17 de CLR. A versão contínua do problema da mochila é resolvida por um algoritmo guloso. A versão booleana é resolvida via programação dinâmica (que pode ser muito lento!).
Dados vetores x[1..n] e w[1..n], vamos denotar por x·w o produto escalar de x por w:
x·w = x[1]w[1] + . . . + x[n]w[n] .
Suponha dado um número inteiro não negativo W e vetores inteiros não negativos w[1..n] e v[1..n] . Uma mochila é qualquer vetor x[1..n] tal que
x·w <= W e 0 <= x[i] <= 1 para todo i.
O valor de uma mochila x é o número x·v. O PROBLEMA CONTÍNUO (ou fracionário) da mochila consiste no seguinte:
Dados w, v, n e W, encontrar uma mochila de valor máximo.
A versão booleana, ou zero-um, do problema tem uma restrição adicional: para todo i,
x[i] = 0 ou x[i] = 1 .
Imagine que sua mochila é um disquete. Suponha que a capacidade do disquete é W. Suponha que tenho n arquivos e cada arquivo i tem tamanho w[i] e valor v[i]. Minha tarefa é produzir um disquete que tenha o maior valor possível. A variável x seleciona os arquivos: o arquivo i é gravado no disquete se e só se x[i]=1.
A versão contínua do problema é um pouco artificial pois permite gravar no disquete apenas uma parte de um arquivo.
Suponha W = 50 e n = 4. A figura abaixo dá os valores de w[1..4] e v[1..4]. Mais abaixo, temos uma solução x[1..4] do problema contínuo e uma solução x'[1..4] do problema booleano. O valor da mochila contínua é x·v = 1040. O valor da mochila booleana é x'·v = 1000.
| w | 40 | 30 | 20 | 10 |
| v | 840 | 600 | 400 | 100 |
| x | 1 | 1/3 | 0 | 0 |
| x' | 0 | 1 | 1 | 0 |
O seguinte algoritmo guloso resolve a versão contínua do problema da mochila. O algoritmo exige que os dados estejam em ordem decrescente de "valor específico" v/w:
v[1]/w[1] >= v[2]/w[2] >= . . . >= v[n]/w[n]
(para evitar divisão por 0, podemos supor que todos os w[i] são positivos). É nesta ordem "mágica" que está o segredo do funcionamento do algoritmo.
MOCHILA-CONTÍNUA (w, v, W, n)
j := 1
enquanto j <= n e w[j] <= W faça
x[j] := 1
W := W-w[j]
j := j+1
se j <= n então
x[j] := W/w[j]
para k := j+1 até n faça
x[k] := 0
devolva x
Eis uma variante:
MOCHILA-CONTÍNUA (w, v, W, n)
para j := 1 até n faça
se w[j] <= W
então x[j] := 1
W := W-w[j]
senão x[j] := W/w[j]
W := 0
devolva x
O algoritmo é guloso porque abocanha o primeiro objeto viável (na ordem dada), sem se preocupar com o que vai acontecer depois e sem jamais se arrepender do valor atribuído a um componente de x.
Por que o algoritmo dá a resposta correta? Bem . . . Isso é um pouco complicado. É evidente que o algoritmo dá o valor de uma mochila; o difícil é provar que o valor é máximo. O fato é que, no início de cada iteração,
existe uma mochila máxima que contém os itens selecionados pelo algoritmo (e possivelmente mais alguns).
A prova dessa afirmação é surpreendentemente enrolada e será omitida.
É evidente que o consumo de tempo do algoritmo é O(n). Isso não inclui o tempo O(n log(n)) necessário para colocar os objetos em ordem antes de aplicar o algoritmo.
Basta considerar o seguinte exemplo: W=50, n=3 ,
| w= | 40, | 30, | 20, |
| v= | 840, | 600, | 400. |
Observe que os itens 1, 2, 3 estão em ordem decrescente de valor e também em ordem decrescente de "valor específico". Apesar disso, o algoritmo guloso não maximiza x·v. (Num certo sentido, que não tenho paciência para detalhar, o algoritmo guloso produz um machila de valor maximal mas não necessariamente máximo.)
O problema da mochila booleana pode ser resolvido por um algoritmo recursivo. O algoritmo é interessante, mas muito ineficiente.
A idéia da recursão todos já conhecem: se o problema é pequeno, resolva-o diretamente; senão, reduza o problema a um problema menor do mesmo tipo. Qual o problema menor nesse caso? Que tal tentar o problema da mochila com dados
w[1..n-1], v[1..n-1] e W ?
Isso faz sentido, sim, se desistirmos de colocar o objeto n na mochila. Caso contrário, se colocarmos o objeto n na mochila, a capacidade da mochila baixa para W-w[n]. É claro que esta segunda alternativa só faz sentido se w[n] <= W.
Vamos colocar essa idéia em prática para um versão simplificada do problema: nosso algoritmo devolverá apenas o valor x·v de uma mochila de valor máximo.
MOCHILA-B-REC (w, v, n, W)
comentário: devolve o valor de uma mochila de valor máximo
se n = 0
então devolva 0
senão A := MOCHILA-B-REC (w, v, n-1, W)
se w[n] > W
então devolva A
senão B := MOCHILA-B-REC (w, v, n-1, W-w[n]) + v[n]
devolva max(A,B)
O algoritmo é muito ineficiente porque refaz, várias vezes, a solução de vários dos subproblemas. Qual o remédio? Guardar as soluções dos subproblemas em uma tabela. É o que faremos em seguida.
O problema da mochila booleana pode ser resolvido por um algoritmo de programação dinâmica [CLR 17.2-1] que consome O(nW) unidades de tempo. Isso é bem melhor que o algoritmo recursivo, mas não é nenhuma maravilha, porque o consumo de tempo depende de W.
O que é "programação dinâmica"? É uma maneira esperta de transformar recursão em iteração. A idéia é guardar em uma tabela, digamos t, as soluções dos subproblemas do problema. A tabela é definida assim: t[i,Y] é o valor máximo da expressão x[1..i]·v[1..i] sujeita à restrição
x[1..i]·w[1..i] <= Y.
Os possíveis valores de Y são 0,1, . . , W (é claro que isso só funciona porque estamos supondo W inteiro) e os possíveis valores de i são 0,1, . . , n. É importante que 0 seja um possível valor de Y e de i. Por exemplo, se w[1]=0 então t[1,0]=v[1].
É fácil ver que t[0,Y]=0 para todo Y. Se i > 0 então
t[i,Y] = A se w[i]>Y e
t[i,Y] = max(A,B) se w[i]<=Y,
onde A = t[i-1,Y] e B = t[i-1,Y-w[i]] + v[i]. Traduzindo para o português:
Se a mochila máxima para 1, . . ,i não usa i então ela é também uma mochila máxima para 1, . . ,i-1. Se a mochila máxima para 1, . . ,i usa i então ela é a "soma" de i com uma mochila máxima para 1, . . ,i-1.
A partir dessa recorrência é fácil escrever um algoritmo de programação dinâmica para determinar t e o vetor x:
MOCHILA-BOOLEANA (w, v, n, W)
para Y := 0 até W faça
t[0,Y] := 0
para i := 1 até n faça
A := t[i-1,Y]
se w[i] > Y
então B := 0
senão B := t[i-1,Y-w[i]] + v[i]
t[i,Y] := max (A,B)
Y := W
para i := n decrescendo até 1 faça
se t[i,Y] = t[i-1,Y]
então x[i] := 0
senão x[i] := 1
Y := Y-w[i]
devolva x
(Note que a coluna t[,0] não é inicializada com zeros. Ela pode conter elementos não nulos se w[i]=0 para algum i.)
É óbvio que o consumo de tempo do algoritmo é O(nW). Essa complexidade não é satisfatória: imagine que uma mudança trivial em nossa escala de medida de pesos multiplica por 1000 os números w[1], . . , w[n] e W; nosso problema continua essencialmente o mesmo, mas o algoritmo pode consumir 1000 vezes mais tempo!
Exemplo: Suponha que W = 5 e n = 4. Os vetores w e v são dados pela figura esquerda. A figura direita dá a tabela t; mas os números da tabela têm um erro (acidental) que você deve descobrir.
|
|
SOLUÇÃO: Em primeiro lugar, eu diria o que a função faz: "MOCHILA-BOOLEANA recebe um vetor inteiro w[1..n], um vetor inteiro v[1..n] e um número inteiro W e devolve um vetor x[1..n] de 0s e 1s tal que x·w <= W e x·v é máximo."
Depois, eu faria um único comentário no fim do primeiro loop:
"t[i,Y] = valor máximo da expressão
x[1..i]·v[1..i] sujeita à restrição
x[1..i]·w[1..i] <= Y."