Qui lo zaino è come un contenitore o una borsa. Supponiamo di aver fornito alcuni articoli che hanno pesi o profitti. Dobbiamo mettere alcuni oggetti nello zaino in modo tale che il valore totale produca il massimo profitto.

Ad esempio, il peso del contenitore è di 20 kg. Dobbiamo selezionare gli articoli in modo tale che la somma del peso degli articoli sia inferiore o uguale al peso del contenitore e il profitto sia massimo.

Esistono due tipi di problemi con lo zaino:

• 0/1 problema con lo zaino
• Problema dello zaino frazionario

Discuteremo entrambi i problemi uno per uno. Innanzitutto, impareremo il problema dello zaino 0/1.

Qual è il problema dello zaino 0/1?

Il problema dello zaino 0/1 significa che gli oggetti sono completamente riempiti o non ci sono oggetti nello zaino. Ad esempio, abbiamo due articoli che pesano rispettivamente 2 kg e 3 kg. Se prendiamo l'articolo da 2 kg, non potremo prelevare l'articolo da 1 kg dall'articolo da 2 kg (l'articolo non è divisibile); dobbiamo scegliere completamente l'articolo da 2 kg. Questo è un problema con lo zaino 0/1 in cui o scegliamo l'oggetto completamente oppure lo sceglieremo. Il problema dello zaino 0/1 è risolto dalla programmazione dinamica.

Qual è il problema dello zaino frazionario?

Il problema dello zaino frazionario significa che possiamo dividere l’oggetto. Ad esempio, abbiamo un articolo da 3 kg, quindi possiamo prendere l'articolo da 2 kg e lasciare l'articolo da 1 kg. Il problema dello zaino frazionario è risolto dall'approccio Greedy.

Esempio di problema dello zaino 0/1.

Considera il problema avente pesi e profitti sono:

Pesi: {3, 4, 6, 5}

Profitti: {2, 3, 1, 4}

Il peso dello zaino è di 8 kg

Il numero di articoli è 4

Il problema di cui sopra può essere risolto utilizzando il seguente metodo:

X_io= {1, 0, 0, 1}

= {0, 0, 0, 1}

esempio di elenco in Java

= {0, 1, 0, 1}

Quanto sopra sono le possibili combinazioni. 1 indica che l'articolo è stato completamente prelevato e 0 significa che nessun articolo è stato prelevato. Poiché gli elementi sono 4, le combinazioni possibili saranno:

2⁴= 16; COSÌ. Ci sono 16 possibili combinazioni che possono essere realizzate utilizzando il problema precedente. Una volta realizzate tutte le combinazioni, dobbiamo selezionare la combinazione che fornisce il massimo profitto.

Un altro approccio per risolvere il problema è l'approccio di programmazione dinamica. Nell'approccio di programmazione dinamica, il problema complicato viene diviso in sottoproblemi, quindi troviamo la soluzione di un sottoproblema e la soluzione del sottoproblema verrà utilizzata per trovare la soluzione di un problema complesso.

Come è possibile risolvere questo problema utilizzando l'approccio di programmazione dinamica?

Primo,

creiamo una matrice mostrata come di seguito:

Nella matrice sopra, le colonne rappresentano il peso, ovvero 8. Le righe rappresentano i profitti e i pesi degli articoli. Qui non abbiamo preso direttamente il peso 8, il problema è diviso in sottoproblemi, cioè 0, 1, 2, 3, 4, 5, 6, 7, 8. La soluzione dei sottoproblemi verrebbe salvata nel celle e la risposta al problema verrebbero archiviate nella cella finale. Per prima cosa scriviamo i pesi in ordine crescente e i profitti in base ai pesi indicati di seguito:

In_io= {3, 4, 5, 6}

P_io= {2, 3, 4, 1}

La prima riga e la prima colonna sarebbero 0 poiché non esiste alcun elemento per w=0

Quando i=1, W=1

In₁= 3; Poiché abbiamo un solo articolo nel set con peso 3, ma la capacità dello zaino è 1. Non possiamo riempire l'articolo di 3 kg nello zaino di capacità 1 kg, quindi aggiungi 0 in M[1][1] mostrato di seguito :

Quando i = 1, W = 2

In₁= 3; Poiché abbiamo un solo articolo nel set con peso 3, ma la capacità dello zaino è 2. Non possiamo riempire l'articolo di 3 kg nello zaino di capacità 2 kg, quindi aggiungi 0 in M[1][2] mostrato di seguito :

Quando i=1, W=3

In₁= 3; Poiché abbiamo un solo oggetto nel set avente peso pari a 3, e anche il peso dello zaino è 3; quindi, possiamo riempire lo zaino con un oggetto di peso pari a 3. Mettiamo il profitto corrispondente al peso 3, cioè 2 in M[1][3] mostrato di seguito:

Quando i=1, W = 4

_W1= 3; Poiché nel set abbiamo un solo articolo con peso pari a 3 e il peso dello zaino è 4; quindi, possiamo riempire lo zaino con un oggetto di peso pari a 3. Mettiamo il profitto corrispondente al peso 3, cioè 2 in M[1][4] mostrato di seguito:

Quando i=1, W = 5

_W1= 3; Poiché nel set abbiamo un solo oggetto con peso pari a 3 e il peso dello zaino è 5; quindi, possiamo riempire lo zaino con un oggetto di peso pari a 3. Mettiamo il profitto corrispondente al peso 3, cioè 2 in M[1][5] mostrato di seguito:

Quando i = 1, W = 6

_W1= 3; Poiché nel set abbiamo un solo articolo con peso pari a 3 e il peso dello zaino è 6; quindi, possiamo riempire lo zaino con un oggetto di peso pari a 3. Mettiamo il profitto corrispondente al peso 3, cioè 2 in M[1][6] mostrato di seguito:

Quando i=1, W = 7

_W1= 3; Poiché nel set abbiamo un solo articolo con peso pari a 3 e il peso dello zaino è 7; quindi, possiamo riempire lo zaino con un oggetto di peso pari a 3. Mettiamo il profitto corrispondente al peso 3, cioè 2 in M[1][7] mostrato di seguito:

Quando i = 1, W = 8

_W1= 3; Poiché nel set abbiamo un solo articolo con peso pari a 3 e il peso dello zaino è 8; quindi, possiamo riempire lo zaino con un oggetto di peso pari a 3. Mettiamo il profitto corrispondente al peso 3, cioè 2 in M[1][8] mostrato di seguito:

Ora il valore di 'i' viene incrementato e diventa 2.

Quando i = 2, W = 1

Il peso corrispondente al valore 2 è 4, cioè w₂= 4. Poiché nell'insieme abbiamo un solo oggetto di peso pari a 4 e il peso dello zaino è 1, non possiamo mettere l'oggetto di peso 4 in uno zaino, quindi aggiungiamo 0 in M[2][1 ] mostrato come di seguito:

Quando i = 2, W = 2

Il peso corrispondente al valore 2 è 4, cioè w₂= 4. Poiché nell'insieme abbiamo un solo oggetto di peso pari a 4 e il peso dello zaino è 2, non possiamo mettere l'oggetto di peso 4 in uno zaino, quindi aggiungiamo 0 in M[2][2 ] mostrato come di seguito:

Quando i = 2, W = 3

Il peso corrispondente al valore 2 è 4, cioè w₂= 4. Poiché abbiamo due oggetti nell'insieme con pesi 3 e 4, e il peso dello zaino è 3. Possiamo mettere l'oggetto di peso 3 in uno zaino, quindi aggiungiamo 2 in M[2][3] mostrato come di seguito:

Quando i = 2, W = 4

Il peso corrispondente al valore 2 è 4, cioè w₂= 4. Poiché abbiamo due articoli nell'insieme con pesi 3 e 4, e il peso dello zaino è 4. Possiamo mettere l'oggetto di peso 4 in uno zaino poiché il profitto corrispondente al peso 4 è maggiore dell'oggetto di peso 3, quindi aggiungiamo 3 in M[2][4] come mostrato di seguito:

Quando i = 2, W = 5

Il peso corrispondente al valore 2 è 4, cioè w₂= 4. Poiché abbiamo due oggetti nell'insieme con pesi 3 e 4, e il peso dello zaino è 5. Possiamo mettere un oggetto di peso 4 in uno zaino e il profitto corrispondente al peso è 3, quindi aggiungiamo 3 a M[2][5] mostrato come di seguito:

Quando i = 2, W = 6

Il peso corrispondente al valore 2 è 4, cioè w₂= 4. Poiché abbiamo due articoli nell'insieme con i pesi 3 e 4, e il peso dello zaino è 6. Possiamo mettere l'oggetto di peso 4 in uno zaino e il profitto corrispondente al peso è 3, quindi aggiungiamo 3 a M[2][6] mostrato come di seguito:

Quando i = 2, W = 7

Il peso corrispondente al valore 2 è 4, cioè w₂= 4. Poiché abbiamo due oggetti nell'insieme con i pesi 3 e 4, e il peso dello zaino è 7. Possiamo mettere gli oggetti di peso 4 e 3 in uno zaino e i profitti corrispondenti ai pesi sono 2 e 3; pertanto, il profitto totale è 5, quindi aggiungiamo 5 in M[2][7] come mostrato di seguito:

Quando i = 2, W = 8

Il peso corrispondente al valore 2 è 4, cioè w₂= 4. Poiché abbiamo due oggetti nell'insieme con i pesi 3 e 4, e il peso dello zaino è 7. Possiamo mettere gli oggetti di peso 4 e 3 in uno zaino e i profitti corrispondenti ai pesi sono 2 e 3; pertanto, il profitto totale è 5, quindi aggiungiamo 5 in M[2][7] come mostrato di seguito:

Ora il valore di 'i' viene incrementato e diventa 3.

Quando i = 3, W = 1

rimuove l'ultimo carattere dalla stringa

Il peso corrispondente al valore 3 è 5, cioè w₃= 5. Poiché abbiamo tre oggetti nell'insieme con pesi 3, 4 e 5, e il peso dello zaino è 1. Non possiamo mettere nessuno degli oggetti in uno zaino, quindi aggiungiamo 0 in M[3][ 1] mostrato come di seguito:

Quando i = 3, W = 2

Il peso corrispondente al valore 3 è 5, cioè w₃= 5. Poiché abbiamo tre oggetti nell'insieme con peso 3, 4 e 5, e il peso dello zaino è 1. Non possiamo mettere nessuno degli oggetti in uno zaino, quindi aggiungiamo 0 in M[3][ 2] mostrato come di seguito:

Quando i = 3, W = 3

Il peso corrispondente al valore 3 è 5, cioè w₃= 5. Poiché abbiamo tre oggetti nell'insieme di peso rispettivamente 3, 4 e 5 e il peso dello zaino è 3. L'oggetto con peso 3 può essere messo nello zaino e il profitto corrispondente all'oggetto è 2, quindi aggiungiamo 2 in M[3][3] mostrato come di seguito:

Quando i = 3, W = 4

Il peso corrispondente al valore 3 è 5, cioè w₃= 5. Poiché nell'insieme abbiamo tre oggetti di peso 3, 4 e 5 rispettivamente e il peso dello zaino è 4, possiamo mantenere l'oggetto di peso 3 o 4; il profitto (3) corrispondente al peso 4 è maggiore del profitto corrispondente al peso 3, quindi aggiungiamo 3 in M[3][4] come mostrato di seguito:

Quando i = 3, W = 5

Il peso corrispondente al valore 3 è 5, cioè w₃= 5. Poiché nell'insieme abbiamo tre oggetti di peso 3, 4 e 5 rispettivamente e il peso dello zaino è 5, possiamo mantenere l'oggetto di peso 3, 4 o 5; il profitto (3) corrispondente al peso 4 è maggiore dei profitti corrispondenti al peso 3 e 5, quindi aggiungiamo 3 in M[3][5] come mostrato di seguito:

film

Quando i = 3, W = 6

Il peso corrispondente al valore 3 è 5, cioè w₃= 5. Poiché nell'insieme abbiamo tre oggetti di peso 3, 4 e 5 rispettivamente e il peso dello zaino è 6, possiamo mantenere l'oggetto di peso 3, 4 o 5; il profitto (3) corrispondente al peso 4 è maggiore dei profitti corrispondenti al peso 3 e 5, quindi aggiungiamo 3 in M[3][6] come mostrato di seguito:

Quando i = 3, W = 7

Il peso corrispondente al valore 3 è 5, cioè w₃= 5. Poiché abbiamo tre articoli nell'insieme di peso 3, 4 e 5 rispettivamente e il peso dello zaino è 7. In questo caso, possiamo mantenere entrambi gli articoli di peso 3 e 4, la somma del profitto sarebbe uguale a (2 + 3), cioè 5, quindi aggiungiamo 5 in M[3][7] come mostrato di seguito:

Quando i = 3, W = 8

Il peso corrispondente al valore 3 è 5, cioè w₃= 5. Poiché abbiamo tre articoli nell'insieme di peso 3, 4 e 5 rispettivamente e il peso dello zaino è 8. In questo caso, possiamo mantenere entrambi gli articoli di peso 3 e 4, la somma dei il profitto sarebbe uguale a (2 + 3), cioè 5, quindi aggiungiamo 5 a M[3][8] come mostrato di seguito:

Ora il valore di 'i' viene incrementato e diventa 4.

Quando i = 4, W = 1

Il peso corrispondente al valore 4 è 6, cioè w₄= 6. Poiché abbiamo quattro oggetti nell'insieme dei pesi 3, 4, 5 e 6 rispettivamente, e il peso dello zaino è 1. Il peso di tutti gli oggetti è maggiore del peso dello zaino, quindi non possiamo aggiungere qualsiasi oggetto nello zaino; Pertanto, aggiungiamo 0 a M[4][1] mostrato di seguito:

Quando i = 4, W = 2

Il peso corrispondente al valore 4 è 6, cioè w₄= 6. Poiché abbiamo quattro oggetti nell'insieme dei pesi 3, 4, 5 e 6 rispettivamente, e il peso dello zaino è 2. Il peso di tutti gli oggetti è maggiore del peso dello zaino, quindi non possiamo aggiungere qualsiasi oggetto nello zaino; Pertanto, aggiungiamo 0 a M[4][2] mostrato di seguito:

Quando i = 4, W = 3

Il peso corrispondente al valore 4 è 6, cioè w₄= 6. Poiché abbiamo quattro articoli nell'insieme di pesi 3, 4, 5 e 6 rispettivamente e il peso dello zaino è 3. L'articolo con peso 3 può essere messo nello zaino e il profitto corrispondente al il peso 4 è 2, quindi aggiungeremo 2 in M[4][3] come mostrato di seguito:

Quando i = 4, W = 4

Il peso corrispondente al valore 4 è 6, cioè w₄= 6. Poiché abbiamo quattro oggetti nell'insieme di pesi 3, 4, 5 e 6 rispettivamente, e il peso dello zaino è 4. L'oggetto con peso 4 può essere messo nello zaino e il profitto corrispondente al il peso 4 è 3, quindi aggiungeremo 3 in M[4][4] come mostrato di seguito:

Quando i = 4, W = 5

Il peso corrispondente al valore 4 è 6, cioè w₄= 6. Poiché abbiamo quattro articoli nell'insieme di pesi 3, 4, 5 e 6 rispettivamente e il peso dello zaino è 5. L'articolo con peso 4 può essere messo nello zaino e il profitto corrispondente al il peso 4 è 3, quindi aggiungeremo 3 in M[4][5] come mostrato di seguito:

Quando i = 4, W = 6

Il peso corrispondente al valore 4 è 6, cioè w₄= 6. Poiché abbiamo quattro oggetti nell'insieme di pesi 3, 4, 5 e 6 rispettivamente e il peso dello zaino è 6. In questo caso, possiamo mettere nello zaino gli oggetti di peso 3, 4 , 5 o 6 ma il profitto, cioè 4 corrispondente al peso 6 è il più alto tra tutte le voci; pertanto, aggiungiamo 4 in M[4][6] come mostrato di seguito:

Quando i = 4, W = 7

Il peso corrispondente al valore 4 è 6, cioè w₄= 6. Poiché abbiamo quattro elementi nell'insieme dei pesi 3, 4, 5 e 6 rispettivamente e il peso dello zaino è 7. Qui, se aggiungiamo due elementi dei pesi 3 e 4, produrrà il massimo profitto, cioè (2 + 3) è uguale a 5, quindi aggiungiamo 5 a M[4][7] come mostrato di seguito:

Quando i = 4, W = 8

Il peso corrispondente al valore 4 è 6, cioè w₄= 6. Poiché abbiamo quattro elementi nell'insieme dei pesi 3, 4, 5 e 6 rispettivamente e il peso dello zaino è 8. Qui, se aggiungiamo due elementi dei pesi 3 e 4, produrrà il massimo profitto, cioè (2 + 3) è uguale a 5, quindi aggiungiamo 5 a M[4][8] come mostrato di seguito:

Come possiamo osservare nella tabella sopra, 5 è il profitto massimo tra tutte le voci. Il puntatore punta all'ultima riga e all'ultima colonna con valore 5. Ora confronteremo il valore 5 con la riga precedente; se la riga precedente, cioè i = 3, contiene lo stesso valore 5, il puntatore si sposterà verso l'alto. Poiché la riga precedente contiene il valore 5, il puntatore verrà spostato verso l'alto come mostrato nella tabella seguente:

Ancora una volta, confronteremo il valore 5 della riga sopra, ovvero i = 2. Poiché la riga sopra contiene il valore 5, il puntatore verrà nuovamente spostato verso l'alto come mostrato nella tabella seguente:

Ancora una volta, confronteremo il valore 5 della riga sopra, ovvero i = 1. Poiché la riga sopra non contiene lo stesso valore, considereremo la riga i=1 e il peso corrispondente alla riga è 4. Pertanto , abbiamo selezionato il peso 4 e abbiamo rifiutato i pesi 5 e 6 riportati di seguito:

x = {1, 0, 0}

Il profitto corrispondente al peso è 3. Pertanto, il profitto rimanente è (5 - 3) uguale a 2. Ora confronteremo questo valore 2 con la riga i = 2. Poiché la riga (i = 1) contiene il valore 2 ; pertanto, il puntatore si è spostato verso l'alto come mostrato di seguito:

Ancora una volta confrontiamo il valore 2 con la riga sopra, ovvero i = 1. Poiché la riga i = 0 non contiene il valore 2, verrà selezionata la riga i = 1 e verrà mostrato il peso corrispondente a i = 1 sotto:

X = {1, 1, 0, 0}

Il profitto corrispondente al peso è 2. Pertanto, il profitto rimanente è 0. Confrontiamo il valore 0 con la riga sopra. Poiché la riga precedente contiene un valore 0 ma il profitto corrispondente a questa riga è 0. In questo problema vengono selezionati due pesi, ovvero 3 e 4 per massimizzare il profitto.