Implementierung des 0/1-Knapsack-Problems in C/C++ mithilfe der Branch-and-Bound-Methode

Die Idee besteht darin, die Tatsache zu erkennen, dass die Greedy-Methode die beste Lösung für das fraktionierte Rucksackproblem bietet.

Um zu überprüfen, ob ein bestimmter Knoten uns eine bessere Lösung liefern kann, berechnen wir die beste Lösung (je Knoten) mithilfe eines Greedy-Ansatzes. Wenn die Greedy-Methode selbst mehr Lösungen als die bisher beste Lösung berechnet, können wir über die Knoten nicht zu einer besseren Lösung gelangen.

Der vollständige Algorithmus lautet wie folgt:

• Sortieren Sie alle Artikel nach der absteigenden Reihenfolge des Wertes pro Gewichtseinheit, sodass die Obergrenze mithilfe der Greedy-Methode berechnet werden kann.

• Initialisieren Sie den maximalen Gewinn, zum Beispiel maxProfit = 0

• Erstellen Sie eine leere Warteschlange Q.

• Virtuelle Entscheidungsknoten erstellen Bäume und fügen sie in Q ein oder stellen sie in die Warteschlange. Der Gewinn und das Gewicht des virtuellen Knotens sind 0.

• Führen Sie die folgenden Vorgänge aus, wenn Q nicht leer oder leer ist.

  • Das Projekt wurde in Q erstellt. Das Extraktionselement sei u.

  • Berechnen Sie den Gewinn des Knotens der nächsten Ebene. Wenn der Gewinn höher als maxProfit ist, ändern Sie maxProfit.

  • Berechnen Sie die Grenzen des Knotens der nächsten Ebene. Wenn die Grenze höher als maxProfit ist, fügen Sie den Knoten der nächsten Ebene zu Q hinzu.

  • Betrachten Sie den Fall, in dem der Knoten der nächsten Ebene nicht berücksichtigt oder als Teil der Lösung betrachtet wird, und fügen Sie den Knoten der Warteschlange auf der nächsten Ebene hinzu, aber Gewicht und Gewinn verarbeiten oder berücksichtigen den Knoten der nächsten Ebene nicht.

Abbildung unten –

// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10

Ausgabe

The maximum possible profit = 235

Das obige ist der detaillierte Inhalt vonImplementierung des 0/1-Knapsack-Problems in C/C++ mithilfe der Branch-and-Bound-Methode. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!