DAA - mochila 0-1

Neste tutorial, discutimos anteriormente o problema da mochila fracionária usando a abordagem Greedy. Mostramos que a abordagem Greedy oferece uma solução ótima para a mochila fracionária. No entanto, este capítulo cobrirá 0-1 problema da mochila e sua análise.

Na mochila 0-1, os itens não podem ser quebrados, o que significa que o ladrão deve pegar o item inteiro ou deixá-lo. Esta é a razão por trás de chamá-lo como 0-1 Knapsack.

Portanto, no caso de 0-1 mochila, o valor de x_i pode ser qualquer um 0 ou 1, onde outras restrições permanecem as mesmas.

0-1 A mochila não pode ser resolvida pela abordagem gananciosa. A abordagem gananciosa não garante uma solução ideal. Em muitos casos, a abordagem Greedy pode fornecer uma solução ótima.

Os exemplos a seguir estabelecerão nossa declaração.

Exemplo 1

Vamos considerar que a capacidade da mochila é W = 25 e os itens são os mostrados na tabela a seguir.

Item	UMA	B	C	D
Lucro	24	18	18	10
Peso	24	10	10	7

Sem considerar o lucro por unidade de peso (p_i/w_i), se aplicarmos a abordagem Greedy para resolver este problema, primeiro item Aserá selecionado como contribuirá max _i lucro mãe entre todos os elementos.

Depois de selecionar o item A, nenhum outro item será selecionado. Portanto, para este determinado conjunto de itens, o lucro total é24. Considerando que a solução ideal pode ser alcançada selecionando itens,B e C, onde o lucro total é 18 + 18 = 36.

Exemplo-2

Em vez de selecionar os itens com base no benefício geral, neste exemplo, os itens são selecionados com base na proporção p _i / w _i . Vamos considerar que a capacidade da mochila é W = 60 e os itens são os mostrados na tabela a seguir.

Item	UMA	B	C
Preço	100	280	120
Peso	10	40	20
Razão	10	7	6

Usando a abordagem Greedy, primeiro item Aé selecionado. Então, o próximo itemBé escolhido. Portanto, o lucro total é100 + 280 = 380. No entanto, a solução ideal desta instância pode ser alcançada selecionando itens,B e C, onde o lucro total é 280 + 120 = 400.

Portanto, pode-se concluir que a abordagem Greedy pode não fornecer uma solução ótima.

Para resolver 0-1 Knapsack, abordagem de Programação Dinâmica é necessária.

Declaração do Problema

Um ladrão está roubando uma loja e pode transportar um máximo _i peso mal deWem sua mochila. temn itens e peso de i^th item é w_i e o lucro de selecionar este item é p_i. Quais itens o ladrão deve levar?

Abordagem de programação dinâmica

Deixei i ser o item de maior número em uma solução ideal S para Wdólares. EntãoS^' = S - {i} é uma solução ótima para W - w_i dólares e o valor da solução S é V_i mais o valor do subproblema.

Podemos expressar esse fato na seguinte fórmula: definir c[i, w] ser a solução para itens 1,2, … , ie o máximo _i peso mamãw.

O algoritmo usa as seguintes entradas

• O max _i peso mamãW

• O número de itens n

• As duas sequências v = <v₁, v₂, …, v_n> e w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if wi ≤ w then 
         if vi + c[i-1, w-wi] then 
            c[i, w] = vi + c[i-1, w-wi] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

O conjunto de itens a serem levados pode ser deduzido da tabela, começando em c[n, w] e rastreando para trás de onde os valores ideais vieram.

Se c [i, w] = c [i-1, w] , então o itemi não faz parte da solução, e continuamos rastreando com c[i-1, w]. Caso contrário, itemi é parte da solução e continuamos rastreando com c[i-1, w-W].

Análise

Esse algoritmo leva θ ( n , w ) vezes, pois a tabela c tem ( n + 1). ( W + 1) entradas, onde cada entrada requer θ (1) tempo para ser computada.