Il problema dello zaino
Ho trovato il problema dello zaino complicato e interessante allo stesso tempo. Sono sicuro che se stai visitando questa pagina, conosci già l’istruzione del problema, ma solo per il completamento :
Problema:
Dato uno zaino di una capacità massima di W e N elementi ciascuno con il proprio valore e peso, inserisci gli elementi all’interno dello zaino in modo tale che il contenuto finale abbia il valore massimo. Accidenti !!,
Ecco il modo generale in cui viene spiegato il problema: considera che un ladro entra in una casa per rubare e porta uno zaino. Ci sono un numero fisso di articoli 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., Lo prende o lo lascia
Esempio :
Knapsack Max weight : W = 10 (units)Total items : N = 4Values of items : v = {10, 40, 30, 50}Weight of items : w = {5, 4, 6, 3}
Uno sguardo superficiale ai dati di esempio ci dice che il valore massimo che potremmo ospitare con il limite di peso massimo di 10 è 50 + 40 = 90 con un peso di 7.
Approccio:
Il modo in cui questo è risolto in modo ottimale sta usando la programmazione dinamica – solving per insiemi più piccoli di problemi a zaino e quindi espandendoli per il problema più grande.,
Costruiamo un array di peso x elemento chiamato V (Value array):
V = 4 rows * 10 columnsCiascuno dei valori in questa matrice rappresenta un problema di zaino più piccolo.
Caso base 1: Prendiamo il caso della 0a colonna. Significa solo che lo zaino ha 0 capacità. Che cosa si può tenere in loro? Niente. Quindi, riempiamoli tutti con 0s.
Caso base 2: prendiamo il caso di 0 riga. Significa solo che non ci sono oggetti in casa. Cosa tieni nello zaino se non ci sono oggetti. Di nuovo niente !!! Tutti gli zeri.,
Soluzione:
1) Ora, iniziamo a compilare la riga dell’array. Cosa significano la riga 1 e la colonna 1? Che dato il primo elemento (riga), si può ospitare nello zaino con capacità 1 (colonna). No. Il peso del primo articolo è 5. Quindi, riempiamo 0. In realtà, non saremmo in grado di compilare nulla fino a raggiungere la colonna 5 (peso 5).
2) Una volta raggiunta la colonna 5 (che rappresenta il peso 5) sulla prima riga, significa che potremmo ospitare l’articolo 1., Riempiamo 10 lì (ricorda, questo è un array di valori):
3) Andando avanti, per il peso 6 (colonna 6), possiamo ospitare qualsiasi altra cosa con il peso rimanente di 1 (peso – peso di questo articolo => 6 – 5). Ehi, ricorda, siamo al primo punto. Quindi, è un po ‘ intuitivo che il resto della riga sarà solo lo stesso valore anche dal momento che non siamo in grado di aggiungere in qualsiasi altro elemento per quel peso extra che abbiamo ottenuto.,
4) Quindi, la prossima cosa interessante accade quando raggiungiamo la colonna 4 in terza riga. Il peso corrente è 4.
Dovremmo verificare i seguenti casi.
1) Possiamo accogliere l’articolo 2-Sì, possiamo. Il peso dell’articolo 2 è 4.
2) Il valore per il peso corrente è più alto senza l’articolo 2? – Controllare la riga precedente per lo stesso peso. No. la riga precedente * ha 0 in esso, dal momento che non siamo stati in grado di ospitare l’articolo 1 in peso 4.
3) Possiamo ospitare due elementi nello stesso peso in modo da poter massimizzare il valore? – No., Il peso rimanente dopo aver dedotto il peso dell’Articolo2 è 0.
Perché la riga precedente?
Semplicemente perché la riga precedente al peso 4 è una soluzione a zaino più piccola che fornisce il valore massimo che potrebbe essere accumulato per quel peso fino a quel punto (attraversando gli elementi).,
Esemplificando,
1) Il valore dell’elemento corrente = 40
2) Il peso dell’elemento corrente = 4
3) Il peso rimasto = 4 – 4 = 0
4) Controlla la riga sopra (l’elemento sopra nel caso dell’elemento 1 o il valore massimo cumulativo nel caso del resto delle righe). Per il peso rimanente 0, siamo in grado di ospitare l’articolo 1? In poche parole, c’è qualche valore nella riga sopra per il peso dato?,
Il calcolo va così:
1) Prendi il valore massimo per lo stesso peso senza questo articolo:
previous row, same weight = 0=> V2) Prendi il valore dell’articolo corrente + valore che potremmo ospitare con il peso rimanente:
Max tra i due è 40 (0 e 40).
3) L’evento successivo e più importante avviene nella colonna 9 e nella riga 2. Significa che abbiamo un peso di 9 e abbiamo due elementi. Guardando i dati di esempio potremmo ospitare i primi due elementi., Qui, consideriamo alcune cose:
- Il valore dell’elemento corrente = 40
- Il peso dell’elemento corrente = 4
- Il peso che rimane = 9 – 4 = 5
- Controlla la riga sopra. Al peso rimanente 5, siamo in grado di ospitare l’articolo 1.
Così, il calcolo è :
1) Prendere il valore massimo per il peso stesso senza questo prodotto:
previous row, same weight = 102) Prendere il valore dell’elemento corrente + il valore che si potrebbe accumulare con i restanti peso:
Value of current item (40)+ value in previous row with weight 5 (total weight until now (9) - weight of the current item (4))= 1010 vs 50 = 50.,
Alla fine di risolvere tutti questi problemi più piccoli, abbiamo solo bisogno di restituire il valore in V – Item 4 al peso 10:
Complessità
Analizzare la complessità della soluzione è piuttosto semplice. Abbiamo solo un ciclo per W all’interno di un ciclo di N=> O (NW)
Implementazione:
Ecco che arriva il codice di implementazione obbligatorio in Java: