Knapsack

[JD557]

Eu não queria ter de perguntar isto, mas quantos mais tutoriais leio mais confuso fico...

Alguém me podia explicar como é que se resolvem problemas de knapsack 1-0?

[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 😛 ). 😉

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

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

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