0/1 Rucksack-Problembehebung anhand eines dynamischen Programmierbeispiels

Was ist das Rucksackproblem?

Das Rucksackproblem ist ein klassisches kombinatorisches Optimierungsproblem. Ein Supermarkt n Pakete (n ≤ 100). Paket i Ein Dieb kann kein Gewicht tragen, das die Kapazität M (M ≤ 100) übersteigt. Welche Pakete sollte er mitnehmen, um den Gesamtwert zu maximieren?

Eingang:

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

Ausgang:

• Maximaler Gesamtwert, der innerhalb der Kapazität erzielt werden kann.
• Die genaue Zusammenstellung der Pakete, die der Dieb mitnehmen soll.

Der Rucksackalgorithmus lässt sich in zwei bekannte Varianten unterteilen:

• 0/1 Rucksackproblem Gelöst durch dynamische Programmierung. Jedes Paket wird entweder vollständig mitgenommen oder zurückgelassen – keine Bruchteile und keine Duplikate.
• Bruchteil-Rucksack-Problem Gelöst wird das Problem durch eine Greedy-Strategie. Hierbei kann man einen Teil eines beliebigen Pakets nehmen, um die verbleibende Kapazität auszufüllen.

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

Die Divide-and-Conquer-Methode zerlegt ein großes Problem in Teilprobleme und teilt es so lange weiter, bis jedes Teilproblem einfach zu lösen ist. Einfache Rekursion hingegen löst oft dasselbe Teilproblem mehrfach und ist somit ineffizient.

Die Kernidee der Rucksack-Dynamischen Programmierung besteht darin, jedes gelöste Teilproblem in einer Tabelle zu speichern. Wiederholte Aufrufe lesen die Lösung aus, anstatt sie neu zu berechnen, wodurch eine exponentielle Rekursion in polynomialen Code umgewandelt wird.

Lösen Sie das Rucksackproblem mit dynamischer Programmierung

Um eine Lösung mit dynamischer Programmierung zu entwerfen, befolgen Sie vier Schritte:

• Löse zuerst die kleinsten Teilprobleme.
• Leiten Sie eine Rekursionsformel her, die aus kleineren Teillösungen eine Teillösung erzeugt.
• Die Antworten auf die Teilprobleme werden in einer Tabelle gespeichert, die von unten nach oben mithilfe der Rekursion berechnet wird.
• Stellen Sie die endgültige Antwort anhand der vollständig ausgefüllten Tabelle zusammen.

Analysieren Sie das 0/1-Rucksackproblem

Der optimale Wert hängt von zwei unabhängigen Faktoren ab:

1. Wie viele Pakete werden noch geprüft?
2. Das restliche Gewicht, das der Rucksack noch aufnehmen kann.

Da die Zielfunktion von zwei Größen abhängt, muss die Optionstabelle zweidimensional sein. B[i][j] bezeichnet den Maximalwert bei der Auswahl aus den Paketen {1, …, i} mit Gewichtslimit j.

• Die endgültige Antwort lautet: B[n][M], der beste Gesamtwert über alle n Pakete unter Kapazität M.
• Das insgesamt ausgewählte Gewicht ist stets durch die aktuelle Kapazität begrenzt: B[i][j] ≤ j.

Beispiel: Wenn B[4][10] = 8, dann ist das beste Gesamtgewicht der ersten vier Pakete unter Kapazität 10 8. Einige dieser vier Pakete können übersprungen werden.

Formel zur Berechnung von B[i][j]

• W[i], V[i] sind Gewicht und Wert des Pakets i, wobei i in {1, …, n} liegt.
• M ist das maximale Gewicht, das der Rucksack tragen kann.

Basisfall mit einem Paket: für jede Kapazität j ≥ W[1]:

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

Entscheiden Sie im allgemeinen Fall, ob Paket i unter Kapazität j aufgenommen werden soll:

• Wenn Paket i ist übersprungen, B[i][j] entspricht dem besten Wert unter Verwendung der Pakete {1, …, i-1} bei Kapazität j:

B[i][j] = B[i - 1][j]

• Wenn Paket i ist gemacht (nur zulässig, wenn W[i] ≤ j), B[i][j] gleich V[i] plus dem besten Wert aus den Paketen {1, …, i-1} unter Kapazität j – W[i]:

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

Nimm den größeren der beiden Kandidaten.

Grundlage der dynamischen Programmierung

Die Kombination der beiden Fälle ergibt die vollständige Rekursion:

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

Der Basisfall ist B[0][j] = 0 für jedes j, da Nullpakete unabhängig von der Kapazität den Wert Null ergeben.

Berechnen Sie die Optionstabelle

Erstellen Sie B mithilfe der Rekursion. Sobald B gefüllt ist, steuert dieselbe Tabelle die tracE-Mail, die die ausgewählten Pakete rekonstruiert. Tabelle B hat n + 1 Zeilen und M + 1 Spalten:

• Zeile 0 ist der Basisfall und ist mit Nullen gefüllt.
• Verwenden Sie Zeile 0, um Zeile 1 zu berechnen, Zeile 1, um Zeile 2 zu berechnen, und fahren Sie fort, bis Zeile n vollständig ist.

Tabelle der Optionen

Trace

Sobald B abgeschlossen ist, konzentrieren Sie sich auf B[n][M], der optimale Gesamtwert über alle n Pakete mit der Kapazität M.

• If B[n][M] = B[n-1][M]Paket n wurde nicht ausgewählt, also fortfahren tracing von B[n-1][M].
• If B[n][M] ≠ B[n-1][M]Paket n wurde ausgewählt, also weiter tracing von B[n-1][M – W[n]].

Wiederholen Sie den Vorgang, bis Sie Zeile 0 der Tabelle erreicht haben.

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

Hinweis: immer B[i][j] = B[i-1][j], Paket i ist nicht ausgewählt. Der Wert B[n][M] ist der optimale Gesamtwert, der in den Rucksack gepackt wird.

Schritte für tracdie ausgewählten Pakete:

• Schritt 1: Beginnen wir mit i = n, j = M.
• Schritt 2: Durchsuchen Sie Spalte j von unten nach oben, bis Sie eine Zeile i finden, in der B[i][j] > B[i-1][j] gilt. Markieren Sie Paket i als ausgewählt: Select[i] = true.
• Schritt 3: Aktualisiere j = j – W[i]. Falls j > 0, gehe zurück zu Schritt 2, andernfalls zu Schritt 4.
• Schritt 4: Drucken Sie jedes als ausgewählt markierte Paket aus.

Java Code

Folgende Java Die Methode füllt B[][] von unten nach oben, gibt die Tabelle zur Überprüfung aus und dann traces die ausgewählten Pakete.

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: ");

    int j = M;
    while (n != 0) {
        if (B[n][j] != B[n - 1][j]) {
            System.out.println("\tPackage " + n + " with W = " + W[n - 1] + " and Value = " + V[n - 1]);
            j = j - W[n - 1];
        }
        n--;
    }
}

Funktion knapsackDyProg() in Java

Erklärung des Codes:

1. Tabelle zuweisen B[][] und initialisiere jede Zelle mit 0.
2. Füllen Sie B[][] von unten nach oben mithilfe der Rekursionsformel aus dem vorherigen Abschnitt.
3. Beginnen Sie jede Zelle mit dem Wert „skip package i“. B[i-1][j].
4. Wenn die Auswahl von Paket i möglich ist und einen deutlich besseren Wert liefert, überschreiben Sie die Zelle.
5. TracFüge die ausgewählten Elemente aus Zeile n wieder in Zeile 0 ein.
6. Wird Paket n ausgewählt, verringert sich die verbleibende Kapazität um W[n-1].

Korrekturhinweis: der ursprüngliche Codeausschnitt veränderte Parameter M während ich noch lese B[n][M]Die oben genannte, sicherere Version verwendet einen separaten Cursor. j für die trace.

Das Java Der Treiber führt den Algorithmus an zwei Beispielen aus:

public void run() {
    // First Example
    // int W[] = new int[]{3, 4, 5, 9, 4};
    // int V[] = new int[]{3, 4, 4, 10, 4};
    // int M = 11;

    // Second Example
    int W[] = new int[]{12, 2, 1, 1, 4};
    int V[] = new int[]{4, 2, 1, 2, 10};
    int M = 15;

    int n = V.length;
    knapsackDyProg(W, V, M, n);
}

Ausgabe für das erste 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

Ausgabe für das zweite 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

Zeit- und Speicherkomplexität des 0/1-Rucksackproblems

• Zeitkomplexität: O(n · M) — die beiden verschachtelten Schleifen durchlaufen n Elemente über M+1 Kapazitätszustände.
• Raumkomplexität: O(n · M) für die vollständige Tabelle, reduzierbar auf O(M) durch Keeping nur die vorherige Zeile, wenn tracEin E-Backup ist nicht erforderlich.

Die Laufzeit ist PseudopolynomPolynomial im Wert von M, aber exponentiell in den Bits, die zur Codierung von M verwendet werden. Deshalb bleibt das 0/1-Rucksackproblem NP-schwer, obwohl dynamische Programmierung in der Praxis effizient ist.

Anwendungen des 0/1-Rucksackproblems

• Frachtverladung, Containerbeladung und Kommissionierung im Lager unter Einhaltung von Gewichtsbeschränkungen.
• Budgetaufteilung auf Investitionsprojekte mit fixen Kosten und erwarteter Rendite.
• Zuschnittprobleme in der Fertigung, bei denen einzelne Teile nicht getrennt werden können.
• Kryptographische Verfahren wie Merkle-Hellman, die auf der Rucksack-Härte basieren.
• Ressourcenbeschränkte Planung im Cloud Computing und CPU-Task-Platzierung.
• Merkmalsauswahl beim maschinellen Lernen unter Berücksichtigung eines festen Merkmalsbudgets.

Häufig gestellte Fragen