Risolto il problema dello zaino 0/1 utilizzando l'esempio di programmazione dinamica

By: Sara Chen Sara Chen
Hours aggiornato

Qual è il problema dello zaino?

Problema dello zaino L'algoritmo è un problema molto utile in combinatoria. Nel supermercato ci sono n pacchi (n ≤ 100) il pacco i ha peso W[i] ≤ 100 e valore V[i] ≤ 100. Un ladro irrompe nel supermercato, il ladro non può trasportare un peso superiore a M (M ≤ 100 ). Il problema da risolvere qui è: quali pacchi porterà via il ladro per ottenere il valore più alto?

Ingresso:

  • Il peso massimo M ed il numero di colli n.
  • Array di peso W[i] e valore corrispondente V[i].

Produzione:

  • Massimizzare il valore e il peso corrispondente in termini di capacità.
  • Quali pacchi porterà via il ladro.

L'algoritmo dello zaino può essere ulteriormente suddiviso in due tipi:

  • Il problema dello zaino 0/1 utilizzando la programmazione dinamica. In questo tipo di algoritmo Zaino, ogni pacco può essere preso o non preso. Inoltre, il ladro non può prendere una frazione di un pacco rubato o prendere un pacco più di una volta. Questo tipo può essere risolto mediante l'approccio di programmazione dinamica.
  • Algoritmo del problema dello zaino frazionario. Questo tipo può essere risolto con la Greedy Strategy.

Come risolvere il problema dello zaino utilizzando la programmazione dinamica con esempio

Nella strategia “divide et impera” si divide il problema da risolvere in sottoproblemi. I sottoproblemi vengono ulteriormente suddivisi in sottoproblemi più piccoli. Tale attività continuerà finché non si otterranno sottoproblemi che possono essere risolti facilmente. Tuttavia, nel processo di tale divisione, potresti riscontrare lo stesso problema molte volte.

L'idea di base della programmazione dinamica Knapsack è quella di utilizzare una tabella per memorizzare le soluzioni dei sottoproblemi risolti. Se dovessi affrontare nuovamente un sottoproblema, ti basterà prendere la soluzione nella tabella senza doverla risolvere di nuovo. Pertanto, gli algoritmi progettati dalla programmazione dinamica sono molto efficaci.

Risolvi il problema dello zaino utilizzando la programmazione dinamica

Per risolvere un problema tramite programmazione dinamica, è necessario eseguire le seguenti attività:

  • Trovare soluzioni ai sottoproblemi più piccoli.
  • Scopri la formula (o regola) per costruire una soluzione di sottoproblemi attraverso soluzioni di sottoproblemi anche più piccoli.
  • Crea una tabella che memorizza le soluzioni dei sottoproblemi. Quindi calcola la soluzione del sottoproblema secondo la formula trovata e salvala nella tabella.
  • Dai sottoproblemi risolti si trova la soluzione del problema originale.

Analizza il problema dello zaino 0/1

Analizzando il problema dello Zaino 0/1 utilizzando la programmazione dinamica, puoi trovare alcuni punti notevoli. Il valore dell'algoritmo dello zaino dipende da due fattori:

  1. Quanti pacchetti vengono presi in considerazione
  2. Il peso rimanente che lo zaino può immagazzinare.

Pertanto, hai due quantità variabili.

Con la programmazione dinamica hai informazioni utili:

  1. la funzione obiettivo dipenderà da due quantità variabili
  2. la tabella delle opzioni sarà una tabella bidimensionale.

Se chiamando B[i][j] è il valore massimo possibile selezionando nei pacchetti {1, 2, …, i} con limite di peso j.

  • Il valore massimo se selezionato in n colli con limite di peso M è B[n][M]. In altre parole: quando ci sono i pacchi da scegliere, B[i][j] è il peso ottimale quando il peso massimo dello zaino è j.
  • Il peso ottimale è sempre inferiore o uguale al peso massimo: B[i][j] ≤ j.

Ad esempio: B[4][10] = 8. Significa che nel caso ottimale il peso totale dei colli selezionati è 8, quando ci sono 4 primi colli tra cui scegliere (dal 1° al 4° collo) e il peso massimo dello zaino è 10. Non è necessario che tutti e 4 gli oggetti siano selezionati.

ARTICOLI CORRELATI

Formula per calcolare B[i][j]

Ingresso, definisci:

  • W[i], V[i] sono a loro volta il peso e il valore del collo i, in cui i Formula per calcolare B[i][j]{1, …, n}.
  • M è il peso massimo che lo zaino può trasportare.

Nel caso in cui si abbia semplicemente 1 solo pacchetto tra cui scegliere. Per ogni j si calcola B[1][j]: ovvero il peso massimo dello zaino ≥ il peso del 1° pacco

B[1][j] = W[1]

Con il limite di peso j, le selezioni ottimali tra i pacchetti {1, 2, …, i – 1, i} per avere il valore maggiore avranno due possibilità:

  • Se il collo i non è selezionato, B[i][j] è il valore massimo possibile selezionando tra i colli {1, 2, …, i – 1} con limite di peso j. Hai:
B[i][j] = B[i – 1][j]
  • Se viene selezionato il pacchetto i (ovviamente considerare questo caso solo quando W[i] ≤ j) allora B[i][j] è uguale al valore V[i] del pacchetto i più il valore massimo che si può ottenere selezionando tra colli {1, 2, …, i – 1} con limite di peso (j – W[i]). Cioè, in termini di valore che hai:
B[i][j] = V[i] + B[i – 1][j – W[i]]

A causa della creazione di B[i][j], che è il valore massimo possibile, B[i][j] sarà il massimo dei 2 valori precedenti.

Basi della Programmazione Dinamica

Quindi, devi considerare se è meglio scegliere il pacchetto i oppure no. Da lì hai la formula ricorsiva come segue:

B[i][j]= max(B[i – 1][j], V[i]+B[i – 1][j – W[i]]

È facile vedere B[0][j] = valore massimo possibile selezionando da 0 pacchetto = 0.

Calcola la tabella delle opzioni

Costruisci una tabella di opzioni basata sulla formula ricorsiva sopra. Per verificare se i risultati sono corretti (se non sono esattamente, ricostruisci la funzione obiettivo B[i][j]). Attraverso la creazione della funzione obiettivo B[i][j] e la tabella delle opzioni, orienterai il tracciato.

La tabella delle opzioni B comprende n + 1 righe, M + 1 colonne,

  • In primo luogo, riempito con le basi della programmazione dinamica: la riga 0 include tutti zeri.
  • Utilizzando formule ricorsive, utilizzare la riga 0 per calcolare la riga 1, utilizzare la riga 1 per calcolare la riga 2, ecc.... finché non vengono calcolate tutte le righe.
Calcola la tabella delle opzioni
Tabella delle opzioni

Traccia

Nel calcolare la tabella delle opzioni, ti interessa B[n][M] che è il valore massimo ottenuto selezionando in tutti gli n pacchi con limite di peso M.

  • If B[n][M] = B[n – 1][M] quindi il pacchetto n non è selezionato, si traccia B[n – 1][M].
  • If B[n][M] ≠ B[n – 1][M], si nota che la selezione ottima ha il pacchetto n e la traccia B[n – 1][M – W[n]].

Continua a tracciare fino a raggiungere la riga 0 della tabella delle opzioni.

Algoritmo per cercare la tabella delle opzioni per trovare i pacchetti selezionati

Nota: se B[i][j] = B[i – 1][j], il pacchetto i non è selezionato. B[n][W] è il valore totale ottimale del pacco messo nello zaino.

Passaggi per il tracciamento:

  • Passo 1 : A partire da i = n, j = M.
  • Passo 2 : Cerca nella colonna j, dal basso, trova la linea i tale che B[i][j] > B[i – 1][j]. Contrassegna il pacchetto selezionato i: Seleziona [i] = true;
  • Passo 3 : j = B[i][j] – W[i]. Se j > 0, vai al passaggio 2, altrimenti vai al passaggio 4
  • Passo 4 : in base alla tabella delle opzioni per stampare i pacchetti selezionati.

Java Code

public void knapsackDyProg(int W[], int V[], int M, int n) {
	int B[][] = new int[n + 1][M + 1];
	
	for (int i=0; i<=n; i++)
		for (int j=0; j<=M; j++) {
			B[i][j] = 0;
		}
	
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= M; j++) {
			B[i][j] = B[i - 1][j];
			
			if ((j >= W[i-1]) && (B[i][j] < B[i - 1][j - W[i - 1]] + V[i - 1])) {
				B[i][j] = B[i - 1][j - W[i - 1]] + V[i - 1]; 
			}
			
			System.out.print(B[i][j] + " ");
		}
		System.out.print("\n");
	}
	
	System.out.println("Max Value:\t" + B[n][M]);
	
	System.out.println("Selected Packs: ");
	
	while (n != 0) {
		if (B[n][M] != B[n - 1][M]) {
			System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
			
			M = M - W[n-1];
		}
		
		n--;
	}
}
Funzione zainoDyProg() in Java

Funzione zainoDyProg() in Java

Spiegazione del codice Zaino:

  1. Crea tabella B[][]. Il valore predefinito impostato per ciascuna cella è 0.
  2. Costruisci la tabella B[][] in modo bottom-up. Calcola la tabella delle opzioni con la formula di recupero.
  3. Calcola B[i][j]. Se non selezioni il pacchetto i.
  4. Quindi valuta: se selezioni il pacchetto i, sarà più vantaggioso quindi reimpostare B[i][j].
  5. Traccia la tabella dalla riga n alla riga 0.
  6. Se scegli il pacchetto n. Una volta selezionato il pacchetto n, è possibile aggiungere solo il peso M – W[n – 1].


In questo tutorial, hai due esempi. Ecco il codice Java per eseguire il programma sopra con due esempi:

public void run() {
	/*
	 * Pack and Weight - Value
	 */
	//int W[] = new int[]{3, 4, 5, 9, 4};
	int W[] = new int[]{12, 2, 1, 1, 4};
	
	//int V[] = new int[]{3, 4, 4, 10, 4};
	int V[] = new int[]{4, 2, 1, 2, 10};
	
	/*
	 * Max Weight
	 */
	//int M = 11;
	int M = 15;
	int n = V.length;
	
	/*
	 * Run the algorithm
	 */
	knapsackDyProg(W, V, M, n);
}

Hai l'output:

  • Primo esempio:
0 0 0 3 3 3 3 3 3 3 3 3 
0 0 0 3 4 4 4 7 7 7 7 7 
0 0 0 3 4 4 4 7 7 8 8 8 
0 0 0 3 4 4 4 7 7 10 10 10 
0 0 0 3 4 4 4 7 8 10 10 11 
Max Value:	11
Selected Packs: 
	Package 5 with W = 4 and Value = 4
	Package 2 with W = 4 and Value = 4
	Package 1 with W = 3 and Value = 3
  • Secondo esempio:
0 0 0 0 0 0 0 0 0 0 0 0 4 4 4 4 
0 0 2 2 2 2 2 2 2 2 2 2 4 4 6 6 
0 1 2 3 3 3 3 3 3 3 3 3 4 5 6 7 
0 2 3 4 5 5 5 5 5 5 5 5 5 6 7 8 
0 2 3 4 10 12 13 14 15 15 15 15 15 15 15 15
Max Value:	15
Selected Packs: 
	Package 5 with W = 4 and Value = 10
	Package 4 with W = 1 and Value = 2
	Package 3 with W = 1 and Value = 1
	Package 2 with W = 2 and Value = 2

Potrebbe piacerti: