0/1 Rucksack-Problembehebung anhand eines dynamischen Programmierbeispiels

Was ist das Rucksackproblem?

Rucksackproblem Der Algorithmus ist ein sehr hilfreiches Problem in der Kombinatorik. Im Supermarkt gibt es n Pakete (n ≤ 100), das Paket i hat das Gewicht W[i] ≤ 100 und den Wert V[i] ≤ 100. Ein Dieb bricht in den Supermarkt ein, der Dieb kann kein Gewicht tragen, das mehr als M (M ≤ 100) beträgt ). Das hier zu lösende Problem lautet: Welche Pakete wird der Dieb mitnehmen, um den höchsten Wert zu erzielen?

Eingang:

• Maximales Gewicht M und die Anzahl der Pakete n.
• Array aus Gewicht W[i] und entsprechendem Wert V[i].

Ausgang:

• Maximieren Sie den Wert und das entsprechende Gewicht in der Kapazität.
• Welche Pakete wird der Dieb mitnehmen?

Der Knapsack-Algorithmus kann weiter in zwei Typen unterteilt werden:

• Das 0/1-Knapsack-Problem mit dynamischer Programmierung. Bei diesem Knapsack-Algorithmustyp kann jedes Paket genommen oder nicht genommen werden. Außerdem darf der Dieb nicht einen Bruchteil eines Pakets mitnehmen oder ein Paket mehr als einmal mitnehmen. Dieser Typ kann durch den dynamischen Programmieransatz gelöst werden.
• Algorithmus für fraktioniertes Knapsack-Problem. Dieser Typ kann durch Greedy Strategy gelöst werden.

So lösen Sie das Rucksackproblem mithilfe dynamischer Programmierung anhand eines Beispiels

Bei der Divide-and-Conquer-Strategie teilt man das zu lösende Problem in Teilprobleme auf. Die Teilprobleme werden weiter in kleinere Teilprobleme unterteilt. Diese Aufgabe wird fortgesetzt, bis Sie Teilprobleme erhalten, die leicht gelöst werden können. Bei einer solchen Aufteilung kann es jedoch vorkommen, dass Sie mehrmals auf dasselbe Problem stoßen.

Die Grundidee der dynamischen Knapsack-Programmierung besteht darin, eine Tabelle zu verwenden, um die Lösungen gelöster Teilprobleme zu speichern. Wenn Sie erneut auf ein Teilproblem stoßen, müssen Sie nur die Lösung aus der Tabelle übernehmen, ohne es erneut lösen zu müssen. Daher sind die durch dynamische Programmierung entwickelten Algorithmen sehr effektiv.

Um ein Problem mithilfe dynamischer Programmierung zu lösen, müssen Sie die folgenden Aufgaben ausführen:

• Finden Sie Lösungen für die kleinsten Teilprobleme.
• Finden Sie die Formel (oder Regel) heraus, um eine Lösung eines Teilproblems durch Lösungen selbst kleinster Teilprobleme zu erstellen.
• Erstellen Sie eine Tabelle, in der die Lösungen von Teilproblemen gespeichert sind. Berechnen Sie dann die Lösung des Teilproblems gemäß der gefundenen Formel und speichern Sie sie in der Tabelle.
• Aus den gelösten Teilproblemen finden Sie die Lösung des ursprünglichen Problems.

Analysieren Sie das 0/1-Rucksackproblem

Bei der Analyse des 0/1-Knapsack-Problems mithilfe der dynamischen Programmierung können Sie einige auffällige Punkte feststellen. Der Wert des Rucksackalgorithmus hängt von zwei Faktoren ab:

1. Wie viele Pakete werden berücksichtigt?
2. Das Restgewicht, das der Rucksack aufnehmen kann.

Daher haben Sie zwei variable Größen.

Mit der dynamischen Programmierung verfügen Sie über nützliche Informationen:

1. Die Zielfunktion hängt von zwei variablen Größen ab
2. Die Optionstabelle ist eine zweidimensionale Tabelle.

Wenn B[i][j] aufgerufen wird, ist der maximal mögliche Wert durch Auswahl in Paketen {1, 2, …, i} mit Gewichtsbeschränkung j.

• Der Maximalwert bei Auswahl in n Paketen mit der Gewichtsgrenze M beträgt B[n][M]. Mit anderen Worten: Wenn i Pakete zur Auswahl stehen, ist B[i][j] das optimale Gewicht, wenn das maximale Gewicht des Rucksacks j beträgt.
• Das optimale Gewicht ist immer kleiner oder gleich dem maximalen Gewicht: B[i][j] ≤ j.

Zum Beispiel: B[4][10] = 8. Dies bedeutet, dass im optimalen Fall das Gesamtgewicht der ausgewählten Pakete 8 beträgt, wenn 4 erste Pakete zur Auswahl stehen (1. bis 4. Paket) und das maximale Gewicht des Rucksacks beträgt 10. Es ist nicht notwendig, dass alle 4 Elemente ausgewählt sind.

Formel zur Berechnung von B[i][j]

Eingabe, Sie definieren:

• W[i], V[i] sind wiederum das Gewicht und der Wert des Pakets i, in dem i widersetzte sich
• M ist das maximale Gewicht, das der Rucksack tragen kann.

Für den Fall, dass Sie einfach nur 1 Paket zur Auswahl haben. Sie berechnen B[1][j] für jedes j: was bedeutet, dass das maximale Gewicht des Rucksacks ≥ dem Gewicht des 1. Pakets ist

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

Mit der Gewichtsgrenze j hat die optimale Auswahl unter den Paketen {1, 2, …, i – 1, i}, um den größten Wert zu haben, zwei Möglichkeiten:

• Wenn das Paket i nicht ausgewählt ist, ist B[i][j] der maximal mögliche Wert durch Auswahl unter den Paketen {1, 2, …, i – 1} mit der Gewichtsbeschränkung von j. Du hast:

B[i][j] = B[i – 1][j]

• Wenn Paket i ausgewählt ist (diesen Fall natürlich nur berücksichtigen, wenn W[i] ≤ j), dann ist B[i][j] gleich dem Wert V[i] von Paket i, plus der Maximalwert kann durch Auswahl unter erhalten werden Pakete {1, 2, …, i – 1} mit Gewichtslimit (j – W[i]). Das heißt, in Bezug auf den Wert, den Sie haben:

B[i][j] = V[i] + B[i – 1][j – W[i]]

Aufgrund der Erstellung von B[i][j], dem maximal möglichen Wert, ist B[i][j] der maximale der beiden oben genannten Werte.

Grundlage der dynamischen Programmierung

Sie müssen also überlegen, ob es besser ist, das Paket i zu wählen oder nicht. Von dort aus haben Sie die rekursive Formel wie folgt:

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

Es ist leicht zu erkennen, dass B[0][j] = maximal möglicher Wert ist, indem man aus 0 Paket = 0 auswählt.

Berechnen Sie die Optionstabelle

Sie erstellen eine Optionstabelle basierend auf der obigen rekursiven Formel. Um zu überprüfen, ob die Ergebnisse korrekt sind (falls nicht, erstellen Sie die Zielfunktion B[i][j] neu). Durch die Erstellung der Zielfunktion B[i][j] und der Optionstabelle orientieren Sie sich an der tracing.

Tabelle der Optionen B umfasst n + 1 Zeilen, M + 1 Spalten,

• Zunächst mit den Grundlagen der dynamischen Programmierung gefüllt: Zeile 0 enthält alle Nullen.
• Verwenden Sie rekursive Formeln, verwenden Sie Zeile 0, um Zeile 1 zu berechnen, verwenden Sie Zeile 1, um Zeile 2 zu berechnen usw. … bis alle Zeilen berechnet sind.

Trace

Bei der Berechnung der Optionstabelle sind Sie an B[n][M] interessiert, dem Maximalwert, der bei der Auswahl in allen n Paketen mit der Gewichtsgrenze M erhalten wird.

• If fort= fortwährend– fortwährend Wenn Paket n nicht ausgewählt ist, trace B[n – 1][M].
• If B[n][M] ≠ B[n – 1][M]Sie stellen fest, dass die optimale Auswahl das Paket n und trace B[n – 1][M – W[n]].

Weiter zu trace bis zum Erreichen von Zeile 0 der Optionstabelle.

Algorithmus zum Nachschlagen der Optionstabelle, um die ausgewählten Pakete zu finden

Hinweis: Wenn B[i][j] = B[i – 1][j], wird das Paket i nicht ausgewählt. B[n][W] ist der optimale Gesamtwert des Pakets, das in den Rucksack gesteckt wird.

Schritte für tracing:

• Schritt 1:: Ausgehend von i = n, j = M.
• Schritt 2:: Schauen Sie in Spalte j von unten nach oben, Sie finden die Zeile i mit B[i][j] > B[i – 1][j]. Ausgewähltes Paket markieren i: Select [i] = true;
• Schritt 3:: j = B[i][j] – W[i]. Wenn j > 0, gehe zu Schritt 2, andernfalls zu Schritt 4
• Schritt 4:: Basierend auf der Optionstabelle zum Drucken der ausgewählten Pakete.

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--;
	}
}

Erklärung des Knapsack-Codes:

1. Erstellen Sie Tabelle B[][]. Der Standardwert für jede Zelle ist 0.
2. Erstellen Sie Tabelle B[][] von unten nach oben. Berechnen Sie die Optionstabelle mit der Abrufformel.
3. Berechnen Sie B[i][j]. Wenn Sie das Paket i nicht auswählen.
4. Bewerten Sie dann: Wenn Sie Paket i auswählen, ist dies vorteilhafter als das Zurücksetzen von B[i][j].
5. TracÖffne die Tabelle von Zeile n bis Zeile 0.
6. Wenn Sie Paket Nr. wählen. Sobald Paket n ausgewählt ist, kann nur das Gewicht M – W[n – 1] hinzugefügt werden.

In diesem Tutorial haben Sie zwei Beispiele. Hier ist Java-Code zum Ausführen des obigen Programms mit zwei Beispielen:

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);
}

Sie haben die Ausgabe:

• Erstes Beispiel:

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

• Zweites Beispiel:

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