In questo tutorial precedente abbiamo discusso Frazionaria Zaino problema con approccio generici. Abbiamo dimostrato che l’approccio avido offre una soluzione ottimale per lo zaino frazionato. Tuttavia, questo capitolo riguarderà 0-1 problema zaino e la sua analisi.
Nello zaino 0-1, gli oggetti non possono essere rotti, il che significa che il ladro dovrebbe prendere l’oggetto nel suo complesso o lasciarlo., Questo è il motivo dietro chiamandolo come 0-1 Zaino.
Quindi, in caso di Zaino 0-1, il valore di xi può essere 0 o 1, dove 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 avido può dare una soluzione ottimale.
I seguenti esempi stabiliranno la nostra dichiarazione.
Esempio-1
Consideriamo che la capacità dello zaino è W = 25 e gli elementi sono come mostrato nella seguente tabella.,
| Elemento | A | B | C | D |
|---|---|---|---|---|
| Profitto | 24 | 18 | 18 | 10 |
| Peso | 24 | 10 | 10 | 7 |
Senza considerare il profitto per unità di peso (pi/wi), se si applica Avidi approccio per risolvere questo problema, prima voce di Un verranno selezionati, che potranno contribuire massimo profitto tra tutti gli elementi.,
Dopo aver selezionato l’elemento A, non verrà selezionato più elemento. Quindi, per questo dato insieme di elementi profitto totale è 24. Mentre, 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 pi / wi. Consideriamo che la capacità dello zaino è W = 60 e gli articoli sono come mostrato nella seguente tabella.,
| Item | A | B | C |
|---|---|---|---|
| Price | 100 | 280 | 120 |
| Weight | 10 | 40 | 20 |
| Ratio | 10 | 7 | 6 |
Using the Greedy approach, first item A is selected. Then, the next item B is chosen. Hence, the total profit is 100 + 280 = 380., Tuttavia, la soluzione ottimale di questa istanza può essere ottenuta selezionando gli elementi, B e C, dove il profitto totale è 280 + 120 = 400.
Quindi, si può concludere che l’approccio Avido potrebbe non dare una soluzione ottimale.
Per risolvere lo zaino 0-1, è necessario un approccio di programmazione dinamica.
Dichiarazione del problema
Un ladro sta rapinando un negozio e può portare un peso massimo di W nel suo zaino. Ci sono n articoli e il peso dell’articolo ith è wi e il profitto di selezionare questo articolo è pi. Quali oggetti dovrebbe prendere il ladro?,
Approccio di programmazione dinamica
Lascia che sia l’elemento con il numero più alto in una soluzione ottimale S per W dollars. Quindi S ‘ = S – {i} è una soluzione ottimale per i dollari W – wi e il valore della soluzione S è Vi più il valore del sotto-problema.
Possiamo esprimere questo fatto nella seguente formula: definire c come soluzione per gli articoli 1,2, … , i e il peso massimo w.,
L’algoritmo prende i seguenti ingressi
-
Il peso massimo W
-
Il numero di elementi n
-
Le due sequenze v = <v1, v2, …, vn> e w = <w1, w2, …, wn>
Il set di elementi per prendere, può essere dedotta dalla tabella, a partire c e traccia indietro dove i valori ottimali è venuto da.
Analisi
Questo algoritmo prende θ(n, w) volte come la tabella c ha (n + 1).(w + 1) voci, dove ogni voce richiede θ (1) tempo per calcolare.,