Aggiornamento: Leggi su come ottimizzare lo spazio complessità della programmazione dinamica soluzione nel mio articolo qui.,
Lo Zaino Problema è davvero interessante problema di calcolo combinatorio — per citare Wikipedia,
“dato un insieme di elementi, ciascuno con un peso e un valore, determinare il numero di ogni elemento da includere in una raccolta, in modo che il peso totale è pari o inferiore ad un determinato limite e il valore totale è il più grande possibile.”
Da Wikipedia, vediamo che ci sono alcune varianti del problema dello zaino: zaino 0-1, zaino limitato e zaino illimitato., Oggi ci concentreremo sulla variante più comune( e più semplice): il problema dello zaino 0-1.
Un fraseggio leggermente più interessante e riconoscibile del problema dello zaino 0-1 è:
Considera che un ladro entra in una casa per rubare e porta uno zaino. Ci sono numero fisso di elementi in casa-ognuno con il proprio peso e valore — Gioielli, con meno peso e più alto valore vs tavoli, con meno valore ma molto pesante. Per aggiungere carburante al fuoco, il ladro ha un vecchio zaino che ha una capacità limitata., Ovviamente, non può dividere il tavolo in metà o gioielli in 3 / 4ths. O lo prende o lo lascia. Source
Sfortunatamente, ho avuto qualche difficoltà a comprendere alcune parti dell’articolo di Hackerearth, motivo per cui ho deciso di scrivere il mio articolo. Questo articolo sarà in gran parte basato sull’articolo di Hackerearth e i frammenti di codice sono scritti in Java. Sarò virare su ulteriori spiegazioni ed elaborazioni dove sento che sono necessari.
Risolveremo questo problema con la programmazione dinamica., La programmazione dinamica richiede una sottostruttura ottimale e sottoproblemi sovrapposti, entrambi presenti nel problema dello zaino 0-1, come vedremo.
Va bene se non capisci cosa sono “sottostruttura ottimale” e “sottoproblemi sovrapposti” (questo è un articolo per un altro giorno). In sostanza, significa solo un particolare sapore di problemi che ci permettono di riutilizzare soluzioni precedenti a problemi più piccoli al fine di calcolare una soluzione al problema attuale. Vedrai cosa intendo tra un po’.,
Dettagli del problema
Poiché questo è il problema dello zaino 0-1, possiamo includere un elemento nel nostro zaino o escluderlo, ma non includerne una frazione, o includerlo più volte.
Soluzione
Innanzitutto, creiamo un array 2-dimensionale (cioè una tabella) din + 1 righe ew + 1 colonne.
Un numero di riga i rappresenta l’insieme di tutti gli elementi delle righe 1— i. Ad esempio, i valori nella riga 3 presuppongono che abbiamo solo elementi 1, 2 e 3.
Un numero di colonna j rappresenta la capacità di peso del nostro zaino., Pertanto, i valori nella colonna 5, ad esempio, presuppongono che il nostro zaino possa contenere 5 unità di peso.
Mettendo tutto insieme, una voce nella riga i, colonna j rappresenta il valore massimo che può essere ottenuto con gli articoli 1, 2, 3 i i, in uno zaino che può contenere unità di peso j.
Chiamiamo la nostra tabella mat per matrix. Pertanto, int mat = new int.
Passo 2:
Possiamo iniziare immediatamente a riempire alcune voci nella nostra tabella: i casi base, per i quali la soluzione è banale., Ad esempio, alla riga 0, quando non abbiamo elementi da scegliere, il valore massimo che può essere memorizzato in qualsiasi zaino deve essere 0. Allo stesso modo, alla colonna 0, per uno zaino che può contenere 0 unità di peso, il valore massimo che può essere memorizzato in esso è 0. (Stiamo supponendo che non ci siano oggetti di valore senza massa.)
Possiamo farlo con 2 cicli for:
Passo 3 (il punto cruciale del problema):
Ora, vogliamo iniziare a compilare la nostra tabella., Come con tutte le soluzioni di programmazione dinamica, ad ogni passo, faremo uso delle nostre soluzioni ai precedenti sotto-problemi.
Prima descriverò la logica, prima di mostrare un esempio concreto.
La relazione tra il valore alla riga i, colonna j e i valori ai precedenti sotto-problemi è la seguente:
Ricordiamo che alla riga i e colonna j, stiamo affrontando un sotto-problema costituito da elementi 1, 2, 3 with i con uno zaino di capacità j. Ci sono 2 opzioni a questo punto: possiamo includere l’elemento i o no., Pertanto, dobbiamo confrontare il valore massimo che possiamo ottenere con e senza item i.
Il valore massimo che possiamo ottenere senza item i può essere trovato alla riga i-1, colonna j. Questa parte è facile. Il ragionamento è semplice: qualunque sia il valore massimo che possiamo ottenere con gli articoli 1, 2, 3 … io ovviamente deve essere lo stesso valore massimo che possiamo ottenere con gli articoli 1, 2, 3 … i – 1, se scegliamo di non comprendono la voce che ho.
Per calcolare il valore massimo che si può ottenere con la voce che ho, abbiamo prima bisogno di confrontare il peso della voce io con lo zaino della capacità di peso., Ovviamente, se l’articolo i pesa più di quello che lo zaino può contenere, non possiamo includerlo, quindi non ha senso eseguire il calcolo. In tal caso, la soluzione a questo problema è semplicemente il valore massimo che possiamo ottenere senza l’elemento i (cioè il valore nella riga sopra, nella stessa colonna).
Tuttavia, supponiamo che l’oggetto i pesa meno della capacità dello zaino. Abbiamo quindi la possibilità di includerlo, se potenzialmente aumenta il valore massimo ottenibile., Il valore massimo ottenibile includendo l’articolo i è quindi = il valore dell’articolo i stesso + il valore massimo che può essere ottenuto con la capacità residua dello zaino. Ovviamente vogliamo sfruttare appieno la capacità del nostro zaino, e non lasciare che qualsiasi capacità residua vada sprecata.
Pertanto, alla riga i e alla colonna j (che rappresenta il valore massimo che possiamo ottenere lì), sceglieremo il valore massimo che possiamo ottenere senza l’elemento i o il valore massimo che possiamo ottenere con l’elemento i, a seconda di quale sia maggiore.
Ecco un esempio concreto di ciò che intendo.,
Alla riga 3 (articolo 2), e la colonna 5 (zaino capacità di 4), possiamo scegliere di includere l’articolo 2 (che pesa 4 unità) o non. Se scegliamo di non includerlo, il valore massimo che possiamo ottenere è lo stesso di se abbiamo solo l’elemento 1 tra cui scegliere (che si trova nella riga sopra, cioè 0)., Se vogliamo includere l’articolo 2, il valore massimo che possiamo ottenere con l’articolo 2 è il valore dell’articolo 2 (40) + il valore massimo che possiamo ottenere con la capacità rimanente (che è 0, perché lo zaino è già completamente pieno).
Alla riga 3 (articolo 2) e alla colonna 10 (capacità dello zaino di 9), di nuovo, possiamo scegliere di includere l’articolo 2 o meno. Se scegliamo di non farlo, il valore massimo che possiamo ottenere è lo stesso di quello nella riga sopra alla stessa colonna, cioè 10 (includendo solo l’elemento 1, che ha un valore di 10). Se includiamo l’articolo 2, abbiamo una capacità residua dello zaino di 9-4 = 5., Possiamo scoprire il valore massimo che può essere ottenuto con una capacità di 5 guardando la riga sopra, alla colonna 5. Pertanto, il valore massimo che possiamo ottenere includendo l’articolo 2 è 40 (il valore dell’articolo 2) + 10 = 50.
Scegliamo il più grande di 50 vs 10, e quindi il valore massimo che possiamo ottenere con gli articoli 1 e 2, con una capacità dello zaino di 9, è 50.,
L’algoritmo può essere espresso in Java come questo:
Fase 4 (soluzione finale):
una Volta che la tabella è stata compilata, la soluzione finale può essere trovato all’ultima riga dell’ultima colonna, che rappresenta il massimo valore ottenibile con tutti gli elementi e la piena capacità dello zaino.
return mat;
Codice di lavoro:
Nota: qui, ho stampato la risposta finale invece di restituirla, poiché tutto è alloggiato sotto public static void main.,
Thanks for reading!