Jump to content
Sign in to follow this  
JD557

Knapsack

Recommended Posts

Tharis

Knapsack 1-0 é o problema mais básico de Programação Dinâmica.

O problema C da qualificação do ano passado é um Knapsack e mais simples até porque o peso é igual ao ganho.

Basicamente tens uma relação tipo esta:

dp(n,w) = max ( dp(n-1, w-pesos[ i ]) + pesos[ i ] , dp(n-1, w) );

n = número de sacos utilizados até agora

w = máximo peso que se pode levar

pesos [ i ] = peso do saco i

Ou seja, tás a calcular a partir de cálculos anteriores. B)

Acho que não me enganei... Até porque tenho pouca experiência em knapsack.... :)

(O pcaldeira, o mogers, o Warrior devem vir aí já fazer-te um bom post) :)

EDIT:

Para calculares fazes dois fors encadeados, um para percorrer os sacos e outro para percorrer os pesos de 1 (já que se o máximo for 0, só levas 0 :P ). ;)

Share this post


Link to post
Share on other sites
Warrior

Knapsack 0-1 não é o problema mais fácil de DP.. é um problema clássico, mas a sua formulação não é completamente evidente para quem tem pouca prática.

A expressão do Tharis está correcta (apesar que o "n" não é o número de sacos, mas sim até que objecto processaste), vou tentar explica-la.

Explicando o problema: tens uma mochila (bag) de capacidade K (neste caso, limite de peso). Tens N itens, cada com um custo (neste caso, o peso) w(i) e com um valor v(i).

O que tu pretendes é saber qual é o maior valor que consegues colocar na mochila.

O truque é perceber que, em qualquer momento, só precisas de saber o peso total da mochila e os objectos que já tentaste pôr para definir o estado do teu programa. Se os tentares colocar por ordem (o mais natural), então só necessitas de manter K mochilas "virtuais" às quais vais tentar acrescentar o teu novo objecto.

Simplificando.

Teremos uma matriz dp(n, k). dp(i, j) representa o maior valor que podes colocar na mochila usando os primeiros "i" objectos, mas limitando a tua mochila a "j". Obviamente que a tua resposta estará em dp(n, k).

Se conseguires construir esta matriz, resolveste o teu problema, e tu consegues preencher alguns valores, ou seja, os casos base.

dp(0, i) = 0 para qualquer i. (usando 0 itens tens valor máximo 0)

dp(i, 0) = 0 para qualquer i. (se não podes colocar nada na mochila (capacidade 0) o valor também será 0, assumindo que os pesos são todos positivos)

Como construir daí para a frente? Vamos imaginar que queres colocar o item "i" na mochila "j".

Tens duas opções: ou o colocas ou não. O que tu queres é aquela que te dá o maior valor.

Se o colocares, qual o novo valor máximo da mochila? Será o máximo que conseguias obter com os primeiros n-1 objectos, mas desta vez não tens o mesmo espaço! Tens somente "j - w(i)", sendo que w(i) é o peso do objecto "i". Se o colocas, tens menos espaço na mochila! Então, será dp(i-1, j - w(i) ) (o máximo anterior) + v(i) (o valor do novo objecto)

E se não o colocares? Então ficas simplesmente com o valor anterior, dp(i-1, j).

Resumindo:

dp(i, j) = max ( dp(i-1, j - w(i) ) + v(i)  ,  dp(i-1, j) )

Construindo a matriz (dois ciclos) tens o problema resolvido.

Share this post


Link to post
Share on other sites
JD557

Sim, até aí já eu tinha entendido relativamente bem... só que acho que esse algoritmo que mostras não impede que se repitam objectos...

É essa a parte que me deixa realmente confuso... tenho de criar um vector que diga para cada valor de dp(n,w) os sacos usados?

Todos os tutoriais que vejo penso que dizem contemplar esses casos, mas não vejo nenhuma razão para isso acontecer B)

EDIT: Parece que o Warrior já respondeu à questão.

Obrigado pelas respostas.


MIEIC @ FEUP

http://project557.blogspot.com/ --- Development Blog

Proteja a sua pen: http://lastknight.pt.vu

Share this post


Link to post
Share on other sites
Tharis

@Warrior, pois... Eu quando me referi "número de" era a contar do 0, mas pronto, eu nunca fui bom a explicar-me.

BTW, esse post ficava muito bem na wiki ou como um mini-tutorial.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.