DAA - 0-1 Zaino

In questo tutorial, in precedenza abbiamo discusso il problema dello zaino frazionario utilizzando l'approccio Greedy. Abbiamo dimostrato che l'approccio Greedy fornisce una soluzione ottimale per Fractional Knapsack. Tuttavia, questo capitolo tratterà il problema dello zaino 0-1 e la sua analisi.

Nello zaino 0-1, gli oggetti non possono essere rotti, il che significa che il ladro dovrebbe prendere l'oggetto nella sua interezza o lasciarlo. Questo è il motivo per chiamarlo 0-1 Knapsack.

Quindi, in caso di 0-1 Knapsack, il valore di x_i possono essere entrambi 0 o 1, dove gli altri vincoli rimangono gli stessi.

Lo zaino 0-1 non può essere risolto con un approccio avido. L'approccio avido non garantisce una soluzione ottimale. In molti casi, l'approccio Greedy può fornire una soluzione ottimale.

I seguenti esempi stabiliranno la nostra dichiarazione.

Esempio 1

Si consideri che la capacità dello zaino è W = 25 e gli articoli sono come mostrato nella tabella seguente.

Senza considerare il profitto per unità di peso (p_i/w_i), se applichiamo l'approccio Greedy per risolvere questo problema, primo elemento Asaranno selezionati in quanto contribuirà massimo _i profitti mamma tra tutti gli elementi.

Dopo aver selezionato l'elemento A, non verrà selezionato più alcun elemento. Quindi, per questo dato insieme di elementi il ​​profitto totale è24. Considerando che, la soluzione ottimale può essere ottenuta selezionando gli articoli,B e C, dove il profitto totale è 18 + 18 = 36.

Esempio-2

Invece di selezionare gli elementi in base al vantaggio complessivo, in questo esempio gli elementi vengono selezionati in base al rapporto p _i / w _i . Si consideri che la capacità dello zaino è W = 60 e gli articoli sono come mostrato nella tabella seguente.

Usando l'approccio Greedy, primo elemento Aè selezionato. Quindi, l'elemento successivoBè scelto. Quindi, il profitto totale è100 + 280 = 380. Tuttavia, la soluzione ottimale di questa istanza può essere ottenuta selezionando elementi,B e C, dove si trova il profitto totale 280 + 120 = 400.

Quindi, si può concludere che l'approccio Greedy potrebbe non fornire una soluzione ottimale.

Per risolvere lo zaino 0-1, è richiesto l'approccio della programmazione dinamica.

Dichiarazione problema

Un ladro sta derubando un negozio e può trasportare un massimo _i peso mal diWnello zaino. Ci sonon articoli e peso di i^th l'oggetto è w_i e il profitto della selezione di questo articolo è p_i. Quali oggetti dovrebbe prendere il ladro?

Approccio alla programmazione dinamica

Permettere i essere l'elemento con il numero più alto in una soluzione ottimale S per Wdollari. PoiS^' = S - {i} è una soluzione ottimale per W - w_i dollari e il valore della soluzione S è V_i più il valore del problema secondario.

Possiamo esprimere questo fatto nella seguente formula: definire c[i, w] per essere la soluzione per gli oggetti 1,2, … , ie il massimo _che peso mammaw.

L'algoritmo accetta i seguenti input

• Il massimo _i peso mammaW

• Il numero di elementi n

• Le due sequenze 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]

L'insieme di elementi da prendere può essere dedotto dalla tabella, a partire da c[n, w] e risalendo all'indietro da dove provengono i valori ottimali.

Se c [i, w] = c [i-1, w] , allora elementoi non fa parte della soluzione e continuiamo a tracciare con c[i-1, w]. Altrimenti, articoloi è parte della soluzione e continuiamo a tracciare con c[i-1, w-W].

Analisi

Questo algoritmo richiede θ ( n , w ) volte poiché la tabella c ha ( n + 1). ( W + 1) voci, dove ogni voce richiede θ (1) tempo per essere calcolata.