Aula sobre Knapsack

Prévia do material em texto

KNAPSACK
rbl@cin.ufpe.br
IF672 – Algoritmos e Estruturas de Dados
   
KNAPSACK
Imagine que você é um ladrão e 
acabou de assaltar uma loja. Você tem 
pouco tempo para decidir o que vai 
levar, pois a polícia está a caminho.
Tudo o que você possui é uma 
mochila, de capacidade limitada, e pode 
escolher entre um conjunto de itens, 
cada um com um lucro associado. Você 
terá também um computador para 
resolver o problema em tempo hábil 
através do algoritmo knapsack. :)
Determine o maior lucro possível que 
você pode obter nesta situação.
   
KNAPSACK
A idéia do algoritmo: você vai 
tentar inserir um item se houver 
capacidade suficiente na sua mochila. 
Em seguida, verificar qual é a melhor 
situação possível: manter a 
configuração de uma mochila com 
capacidade menor, possivelmente com o 
item, manter a configuração passada 
com uma mochila de capacidade igual à 
avaliada, sem o item, ou inserir o item 
desejado numa mochila que não tinha o 
item mas que possui espaço disponível 
para comportá-lo.
   
KNAPSACK
Para isso, usaremos uma tabela que 
guardará o maior lucro que é possível 
obter com uma mochila de capacidade 
C e com os itens de 1 a R.
Exemplo ilustrativo a seguir:
R=1 C=1R=1 C=1 R=1 C=2R=1 C=2R=1 C=1R=1 C=1 R=1 C=3R=1 C=3
R=2 C=1R=2 C=1 R=2 C=2R=2 C=2
R=1 C=1R=1 C=1
R=2 C=3R=2 C=3
R=1 C=1R=1 C=1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Então, no campo R=1 C=1, temos uma 
mochila de capacidade 1 (ou seja, o 
peso dos itens não pode ultrapassar 1) 
e neste ponto só tentamos colocar até 
o item #1.
R=1 C=1R=1 C=1 R=1 C=2R=1 C=2R=1 C=1R=1 C=1 R=1 C=3R=1 C=3
R=2 C=1R=2 C=1 R=2 C=2R=2 C=2
R=1 C=1R=1 C=1
R=2 C=3R=2 C=3
R=1 C=1R=1 C=1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
No campo R=1 C=2, temos uma 
mochila de capacidade 2 com itens até 
o item #1 (porque ainda estamos na 
linha R=1). O mesmo raciocínio é válido 
para R=1 C=3.
R=1 C=1R=1 C=1 R=1 C=2R=1 C=2R=1 C=1R=1 C=1 R=1 C=3R=1 C=3
R=2 C=1R=2 C=1 R=2 C=2R=2 C=2
R=1 C=1R=1 C=1
R=2 C=3R=2 C=3
R=1 C=1R=1 C=1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Agora, vamos para a próxima linha. 
A partir de agora, podemos usar o 
item #2. Mas precisamos combiná-lo 
com a possibilidade de também usar o 
item #1, certo?
R=1 C=1R=1 C=1 R=1 C=2R=1 C=2R=1 C=1R=1 C=1 R=1 C=3R=1 C=3
R=2 C=1R=2 C=1 R=2 C=2R=2 C=2
R=1 C=1R=1 C=1
R=2 C=3R=2 C=3
R=1 C=1R=1 C=1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Quando estou em R=2 C=1, eu tenho 
uma mochila de capacidade 1, 
possivelmente com os itens do #1 ao 
#2. Entendeu o significado de R 
(linha)?
R=1 C=1R=1 C=1 R=1 C=2R=1 C=2R=1 C=1R=1 C=1 R=1 C=3R=1 C=3
R=2 C=1R=2 C=1 R=2 C=2R=2 C=2
R=1 C=1R=1 C=1
R=2 C=3R=2 C=3
R=1 C=1R=1 C=1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Similarmente, quando eu estiver na 
linha R=3 C=3, eu estarei considerando 
a possibilidade de ter os itens do #1 
ao #3, com uma mochila de capacidade 
3.
R=1 C=1R=1 C=1 R=1 C=2R=1 C=2R=1 C=1R=1 C=1 R=1 C=3R=1 C=3
R=2 C=1R=2 C=1 R=2 C=2R=2 C=2
R=1 C=1R=1 C=1
R=2 C=3R=2 C=3
R=1 C=1R=1 C=1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Agora, vamos a um exemplo prático 
para entender o raciocínio por trás da 
tabela. Vamos começar preenchendo a 
primeira linha...
Item #1: Peso 2, Lucro 4
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
R=2 C=1R=2 C=1 R=2 C=2R=2 C=2 R=2 C=3R=2 C=3
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Veja que só é possível inserir o 
item #1 a partir da coluna 2 (que tem 
capacidade suficiente para comportar o 
item). Nosso lucro, até então, é 4.
Item #1: Peso 2, Lucro 4
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
R=2 C=1R=2 C=1 R=2 C=2R=2 C=2 R=2 C=3R=2 C=3
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Vamos agora inserir o item #2. Como 
nossa melhor mochila de capacidade 1 
tem lucro 0, podemos inserir o item #2 
sem medo em R=2 C=1
Item #2: Peso 1, Lucro 1
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Agora, temos uma escolha a fazer: 
manter a mochila com itens até #2 de 
capacidade inferior (neste caso, cap 1), 
ou pegar o melhor com a capacidade 
atual, sem o item #2 (linha anterior).
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
???
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Para tomar a escolha, pegamos aquela 
que dá o maior lucro... neste caso, 
ficaremos com lucro 4 e com item #1 
mesmo (linha anterior).
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Agora, temos uma mochila de cap. 3 
que pode ter os itens do #1 ao #2... 
precisamos escolher: manter o lucro 
obtido com capacidade menor (coluna 
anterior) com até o item #2 ou...
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
???
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Ou manter o maior lucro obtido com 
uma mochila de mesma capacidade, mas 
sem a possibilidade de ter o item #2 
(linha anterior)...?
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
???
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
KNAPSACK
Que tal então, combinar os itens? Mas 
como fazer isso afinal? Você quer 
adicionar o item #2 de cap. 1. Para 
isso, é preciso garantir que onde você 
inserir, lá tenha capacidade suficiente.
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
???
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
   
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
???
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
KNAPSACK
Façamos assim: vamos garantir que 
não temos o item #2 (pois vamos 
adicioná-lo agora) e que temos espaço 
de sobra para colocá-lo. Se nossa 
capacidade é 3 no momento e nosso 
item pesa 1, precisaríamos ter no máximo 
2 de peso na nossa mochila. Onde 
encontrar uma posição na tabela que 
represente melhor essa situação?
   
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
???
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
KNAPSACK
Em destaque, temos uma mochila que 
tem no máximo itens que, somados, 
pesam 2 (suficiente para colocar nosso 
novo item), e garantimos que não há o 
item #2 ainda naquele momento.
   
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
Itens = {#1,#2}
Lucro = 4+1 = 5
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
R=3 C=1R=3 C=1 R=3 C=2R=3 C=2 R=3 C=3R=3 C=3
KNAPSACK
Para acrescentar o item, basta somar 
seu lucro ao lucro obtido naquela 
posição destacada. Finalmente, teremos 
os itens #1 e #2 como melhor lucro para 
uma mochila de capacidade 3! :)
   
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
Itens = {#1,#2}
Lucro = 4+1 = 5
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
Itens = {#2}
Lucro = 1
Itens = {#1}
Lucro = 4
KNAPSACK
Vamos agora tentar um novo item, 
dessa vez um pesado suficiente.Neste 
caso, como não há como inserí-lo, 
repetimos o melhor que obtivemos antes:
Item #3: Peso 3, Lucro 8
   
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
Itens = {#1,#2}
Lucro = 4+1 = 5
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
Itens = {#2}
Lucro = 1
Itens = {#1}
Lucro = 4
???
KNAPSACK
Agora precisamos decidir se é melhor 
inserir o novo item na mochila ou se é 
melhor manter o melhor que já 
obtivemos, sem o item #3.
Item #3: Peso 3, Lucro 8
   
Itens = {}
Lucro = 0
Itens = {#1}
Lucro = 4
Itens = {#1}
Lucro = 4
Itens = {#1,#2}
Lucro = 4+1 = 5
Itens = {#1}
Lucro = 4
Itens = {#2}
Lucro = 1
Itens = {#2}
Lucro = 1
Itens = {#1}
Lucro = 4
Itens = {#3}
Lucro = 8
KNAPSACK
Neste caso, vemos que é melhor 
adicionar o novo item #3 na mochila que 
não tem nada (pois com isso haverá 
espaço suficiente), obtendo lucro 0+8.
Item #3: Peso 3, Lucro 8
   
KNAPSACK
Na prática, você só vai guardar o 
valor do lucro nas posições da tabela. 
Apenas para fins didáticos foi 
mostrado o conjunto de itens em cada 
configuração de mochila (células da 
tabela).
Temos que o lucro na mochila é 
calculada da seguinte maneira:
lucro[r][c] = max(lucro[r][c-1], lucro[r-1][c]);
lucro[r][c] = max(..., lucro[r-1][c-peso[r]] + custo[r]);
   
KNAPSACK
Traduzindo:
O lucro numa mochila com itens 
possivelmente até 'r' (1,2,...,r) e com 
capacidade 'c' é o máximo entre o 
lucro de uma mochila com mesma 
possibilidade de itens, mas de cap. 
inferior, ou numa mochila que não tenha 
o item 'r' mas tenha a mesma 
capacidade, ou ainda, numa mochila que 
não tenha o item 'r' e tenha espaço 
suficiente para colocá-lo + seu custo.
lucro[r][c] = max(lucro[r][c-1], lucro[r-1][c]);
lucro[r][c] = max(..., lucro[r-1][c-peso[r]] + custo[r]);
   
KNAPSACK
Alguns cuidados precisam ser 
tomados, principalmente com acesso 
ilegal a array. Para isso, você pode 
criar posições auxiliares com lucro zero 
para facilitar os cálculos (como uma 
mochila de cap. 0 cuja coluna seria 
zerada ou uma mochila com 0 itens, cuja 
linha inicial seria zerada). Da mesma 
forma, cuidado na subtração c-peso[r], 
só tente inserir o item se peso[r] <= 
'c', para assim caber na mochila.
lucro[r][c] = max(lucro[r][c-1], lucro[r-1][c]);
lucro[r][c] = max(..., lucro[r-1][c-peso[r]] + custo[r]);
   
KNAPSACK
Fica um exemplo para ser resolvido 
como exercício. O gabarito está no 
próximo slide. :)
Mochila suporta até 8 de peso. E 
teremos ao todo 5 itens: Item #1 Peso 5 
Custo 1, Item #2 Peso 3 Custo 4, Item 
#3 Peso 1 Custo 3, Item #4 Peso 6 
Custo 10, Item #5 Peso 2 Custo 6. Qual 
é o maior lucro possível?
   
KNAPSACK
C=0 C=1 C=2 C=3 C=4 C=5 C=6 C=7 C=8
R=0 0 0 0 0 0 0 0 0 0
R=1 0 0 0 0 0 1 1 1 1
R=2 0 0 0 4 4 4 4 4 5
R=3 0 3 3 4 7 7 7 7 7
R=4 0 3 3 4 7 7 10 13 13
R=5 0 3 6 9 9 10 13 13 16
PS: neste gabarito, estou usando as linhas e 
colunas auxiliares R=0 e C=0 (sem itens ou 
capacidade zero na mochila).
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28