dynamic-programming
Problema dello zaino

Osservazioni

0-1 Problema dello zaino

Supponiamo che ti venga chiesto, dato il peso totale che puoi portare sullo zaino e alcuni oggetti con il loro peso e i loro valori, come puoi prendere quegli oggetti in modo tale che la somma dei loro valori sia massima, ma la somma dei loro pesi indossi superare il peso totale che puoi trasportare? Lo 0-1 indica che scegli l'oggetto o non lo fai. Inoltre abbiamo una quantità di ogni articolo. Significa che non puoi dividere l'oggetto. Se non si trattava di un problema con lo zaino 0-1 , significa che se aveste potuto dividere gli oggetti, vi sarebbe una soluzione avida, che è chiamata problema dello zaino frazionario .

Per ora concentriamoci sul nostro problema. Ad esempio, supponiamo di avere una capacità dello zaino di 7 . Abbiamo 4 oggetti. I loro pesi e valori sono:

+----------+---+---+---+---+
|   Item   | 1 | 2 | 3 | 4 |
+----------+---+---+---+---+
|  Weight  | 1 | 3 | 4 | 5 |
+----------+---+---+---+---+
|   Value  | 1 | 4 | 5 | 7 |
+----------+---+---+---+---+

Un metodo di forza bruta prenderebbe tutte le possibili combinazioni di elementi. Quindi possiamo calcolare i loro pesi totali ed escluderli che superano la capacità del nostro zaino e scoprire quello che ci dà il massimo valore. Per 4 articoli, dovremo controllare ( 4! - 1 ) = 23 combinazioni possibili (escludendo una senza elementi). Questo è piuttosto ingombrante quando aumenta il numero di elementi. Qui, alcuni aspetti che possiamo notare, cioè:

• Possiamo prendere gli oggetti minori e calcolare il valore massimo che possiamo ottenere usando quegli articoli e combinarli. Quindi il nostro problema può essere suddiviso in sottoproblemi.
• Se calcoliamo le combinazioni per l'elemento {1,2} , possiamo usarlo quando calcoliamo {1, 2, 3} .
• Se riduciamo al minimo il peso e massimizziamo il valore, possiamo scoprire la nostra soluzione ottimale.

Per questi motivi, utilizzeremo la programmazione dinamica per risolvere il nostro problema. La nostra strategia sarà: ogni volta che arriva un nuovo oggetto, controlleremo se possiamo scegliere l'oggetto o meno e di nuovo sceglieremo gli oggetti che ci danno il massimo valore. Ora, se selezioniamo l'articolo, il nostro valore sarà il valore dell'oggetto, più il valore che possiamo ottenere sottraendo il valore dalla nostra capacità e il massimo che possiamo ottenere per quel peso rimanente. Se non selezioniamo l'articolo, sceglieremo gli articoli che ci danno il massimo valore senza includere l'articolo. Proviamo a capirlo con il nostro esempio:

Prenderemo una tabella di array 2D, in cui il numero di colonne sarà il valore massimo che possiamo ottenere prendendo gli elementi + 1. E il numero di righe sarà uguale al numero di elementi. Il nostro array sarà simile a:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

Abbiamo incorporato il peso e il valore di ciascun articolo nell'array per comodità. Ricorda che questi non sono parte dell'array, questi sono solo a scopo di calcolo, non è necessario memorizzare questi valori nell'array di tabella .

La nostra prima colonna è piena di 0 . Significa che se la nostra capacità massima è 0 , indipendentemente dall'elemento che abbiamo, dal momento che non possiamo scegliere alcun oggetto, il nostro valore massimo sarà 0 . Iniziamo dalla tabella [0] [1] . Quando stiamo riempiendo la tabella [1] [1] , ci stiamo chiedendo se la nostra capacità massima fosse 1 e avessimo solo il primo elemento, quale sarebbe il nostro valore massimo? Il meglio che possiamo fare è 1 , scegliendo l'oggetto. Per Table [0] [2] significa che se la nostra capacità massima è 2 e abbiamo solo il primo oggetto, il valore massimo che possiamo ottenere è 1 . Questo sarà lo stesso per Tabella [0] [3] , Tabella [0] [4] , Tabella [0] [5] , Tabella [0] [6] e Tabella [0] [7] . Questo perché abbiamo solo un oggetto, che ci dà valore 1 . Dato che abbiamo solo 1 quantità di ogni oggetto, non importa quanto aumentiamo la capacità del nostro zaino, da un oggetto, 1 è il miglior valore che possiamo fare. Quindi il nostro array sarà simile a:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 |   |   |   |   |   |   |   |
+-------+--------+---+---+---+---+---+---+---+---+

Andando avanti, per Table [1] [1] , ci stiamo chiedendo se avessimo gli item 1 e 2 e se la capacità massima del nostro zaino fosse 1 , qual è il valore massimo che possiamo ottenere? Se prendiamo entrambi gli item 1 e 2 , il peso totale sarà 4 , che supererà la nostra capacità attuale dello zaino. Quindi l'elemento 2 non può essere selezionato. Ora, qual è il meglio che possiamo fare senza prendere l'articolo 2 ? Il valore dall'alto, ovvero Table [0] [1] che contiene il valore massimo che possiamo ottenere se avessimo la massima capacità 1 e non abbiamo scelto il secondo elemento. Per Table [1] [2] , poiché 2 è inferiore al peso [2] , ovvero il peso del secondo elemento, non possiamo prendere l'oggetto. Quindi possiamo stabilire che, se il peso dell'articolo corrente è maggiore della nostra capacità massima, non possiamo prendere quell'oggetto. In questo caso, prenderemo semplicemente il valore dall'alto, che rappresenta il valore massimo che possiamo prendere escludendo l'articolo.

if weight[i] > j
    Table[i][j] := Table[i-1][j]
end if

Ora per Table [1] [3] poiché la nostra capacità massima è uguale al nostro peso attuale, abbiamo due scelte.

• Selezioniamo l'oggetto e aggiungiamo il suo valore con il valore massimo che possiamo ottenere dagli altri oggetti rimanenti dopo aver preso questo oggetto.
• Possiamo escludere questo articolo.

Tra le due scelte, sceglieremo quella da cui possiamo ottenere il massimo valore. Se selezioniamo l'articolo, otteniamo: valore per questo articolo + valore massimo dal resto degli articoli dopo aver preso questo oggetto = 4 + 0 = 4 . Otteniamo 4 (valore dell'oggetto) dalla nostra serie di pesi e lo 0 (il massimo valore che possiamo ottenere dal resto degli articoli dopo aver preso questo oggetto) arriva andando 1 punto sopra e 3 passi indietro. Questa è la tabella [0] [0] . Perché? Se prendiamo l'oggetto, la nostra capacità rimanente sarà 3 - 3 = 0 e l'oggetto rimanente sarà il primo oggetto. Bene, se richiama Tabella [0] [0] memorizza il valore massimo che possiamo ottenere se la nostra capacità fosse 0 e avessimo solo il primo oggetto. Ora, se non selezioniamo l'articolo, il valore massimo che possiamo ottenere proviene da 1 punto sopra, cioè 1 . Ora prendiamo il massimo di questi due valori ( 4 , 1 ) e impostiamo Table [1] [2] = 4 . Per Table [1] [4] , dal 4 , la capacità massima dello zaino è superiore a 3 , il peso del nostro articolo corrente, abbiamo ancora due opzioni. Prendiamo il massimo ( Peso [2] + Tabella [0] [4-Peso [2]] , Tabella [0] [4] ) = massimo ( Peso [2] + Tabella [0] [1] , Tabella [0] [4] ) = max ( 4 + 1 , 1 ) = 5 .

if weight[i] <= j
    w := weight[i]
    Table[i][j] := max(w + Table[i][j-w], Table[i-1][j])
end if

Utilizzando queste due formule, possiamo popolare l'intera matrice di tabella . Il nostro array sarà simile a:

+-------+--------+---+---+---+---+---+---+---+---+
| Value | Weight | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+--------+---+---+---+---+---+---+---+---+
|   1   |    1   | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+-------+--------+---+---+---+---+---+---+---+---+
|   4   |    3   | 0 | 1 | 1 | 4 | 5 | 5 | 5 | 5 |
+-------+--------+---+---+---+---+---+---+---+---+
|   5   |    4   | 0 | 1 | 1 | 4 | 5 | 6 | 6 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+
|   7   |    5   | 0 | 1 | 1 | 4 | 5 | 7 | 8 | 9 |
+-------+--------+---+---+---+---+---+---+---+---+

Qui, l'ultimo valore che abbiamo inserito nel nostro array, Table [3] [7] contiene il nostro valore massimo richiesto. Questo è il valore massimo che possiamo ottenere se avessimo 4 articoli e la nostra capacità massima dello zaino era 7 .

Qui una cosa da ricordare è che, anche per la prima fila, il peso può essere maggiore della capacità dello zaino. Dovremo mantenere un altro vincolo per controllare il valore durante il riempimento della prima riga. Oppure possiamo semplicemente prendere un'altra riga e impostare tutti i valori della prima riga su 0 . Lo pseudo-codice sarà simile a:

Procedure Knapsack(Weight, Value, maxCapacity):
n := Item.size - 1
Table[n+1][maxCapacity+1]
for i from 0 to n
    Table[i][0] := 0
end for
for j from 1 to maxCapacity
    if j >= Weight[0]
        Table[0][j] := Weight[0]
    else
        Table[0][j] := 0
    end if
end for
for i from 1 to n
    for j from 1 to maxCapacity
        if Weight[i] >= j                                            //can't pick the item
            Table[i][j] := Table[i-1][j]        
        else                                                        //can pick the item
            w := Weight[i]
            Table[i][j] := max(w + Table[i-1][j-w], Table[i-1][j])
        end if
    end for
end for
Return Table[n][maxCapacity]

La complessità temporale di questo algoritmo è O(n*maxCapacity) , dove n è il numero di elementi e maxCapacity è la capacità massima del nostro zaino.

Finora, abbiamo trovato il valore massimo che possiamo ottenere dal nostro esempio. Rimane ancora una domanda. Quali sono gli oggetti reali? Ripercorreremo i valori nel nostro array Tabella per scoprire gli elementi che abbiamo preso. Seguiremo due strategie:

• Per ogni articolo, se il valore proviene dalla posizione sopra, non abbiamo preso l'articolo corrente. Facciamo 1 passo sopra.
• Se il valore non proviene dalla posizione sopra, abbiamo preso l'oggetto. Quindi andiamo 1 passo sopra e x passi indietro dove x è il peso della voce corrente.

Lo pseudo-codice sarà:

Procedure printItems(Table, maxCapacity, Value):
i := Item.size - 1
j := maxCapacity
while j is not equal to 0
    if Table[i][j] is equal to Table[i-1][j]
        i := i - 1
    else
        Print: i
        j := j - weight[i]
        i := i - 1
    end if
end while

Se ripercorriamo il nostro esempio, otterremo:

Da questo, possiamo dire che, possiamo prendere gli articoli 2 e 3 per ottenere il valore massimo.