• Zuhause
  • Artikel
  • So lösen Sie das Rucksackproblem mit dynamischer Programmierung
Veröffentlicht am 16-03-2019

So lösen Sie das Rucksackproblem mit dynamischer Programmierung

Das Rucksackproblem ist ein wirklich interessantes Problem in der Kombinatorik - Wikipedia zitieren,

„Wenn Sie einen Satz von Elementen mit jeweils einem Gewicht und einem Wert angeben, legen Sie die Anzahl jedes Elements fest, das in eine Sammlung aufgenommen werden soll, sodass das Gesamtgewicht kleiner oder gleich einer bestimmten Grenze ist und der Gesamtwert so groß wie möglich ist. ”

Aus Wikipedia sehen wir, dass es einige Variationen des Rucksackproblems gibt: 0–1 Rucksack, gebundener Rucksack und unbegrenzter Rucksack. Heute konzentrieren wir uns auf die häufigste (und einfachste) Variante: das 0-1-Rucksackproblem.

Eine etwas interessantere und verständlichere Formulierung des 0-1-Rucksackproblems ist:

Stellen Sie sich vor, ein Dieb kommt in ein Heim, um zu rauben, und er trägt einen Rucksack. Es gibt eine feste Anzahl von Gegenständen in der Wohnung - jedes mit seinem eigenen Gewicht und Wert - Schmuck, mit weniger Gewicht und höchstem Wert, verglichen mit Tischen, mit einem geringeren Wert, aber sehr schwer. Um dem Feuer Brennstoff zu geben, hat der Dieb einen alten Rucksack mit begrenzter Kapazität. Natürlich kann er den Tisch nicht in zwei Hälften oder Schmuck in drei Viertel teilen. Er nimmt es entweder oder verlässt es. Quelle

Leider hatte ich einige Schwierigkeiten, einige Teile des Hackerearth-Artikels zu verstehen, weshalb ich mich entschied, meinen eigenen Artikel zu schreiben. Dieser Artikel basiert weitgehend auf Hackerearths Artikel, und Code-Snippets werden in Java geschrieben. Ich werde auf zusätzliche Erklärungen und Ausführungen eingehen, wo ich es für notwendig halte.

Dynamische Programmierung

Wir lösen dieses Problem mit dynamischer Programmierung. Dynamische Programmierung erfordert eine optimale Unterstruktur und überlappende Unterprobleme, die beide, wie wir sehen werden, im 0-1-Rucksack-Problem vorhanden sind.

Es ist in Ordnung, wenn Sie nicht verstehen, was "optimale Teilstruktur" und "überlappende Teilprobleme" sind (dies ist ein Artikel für einen anderen Tag). Im Wesentlichen handelt es sich dabei lediglich um eine bestimmte Art von Problemen, die es uns ermöglichen, vorherige Lösungen für kleinere Probleme erneut zu verwenden, um eine Lösung für das aktuelle Problem zu berechnen. Sie werden sehen, was ich kurz meine.

Problemdetails

Angenommen, wir haben einen Rucksack, der int w = 10 Gewichtseinheiten aufnehmen kann. Wir haben insgesamt int n = 4 Elemente zur Auswahl, deren Werte durch ein Array int [] val = {10, 40, 30, 50} und Gewichtungen durch ein Array int [] wt = {5, 4 dargestellt werden 6, 3}.

Da dies das 0-1-Rucksack-Problem ist, können wir entweder einen Gegenstand in den Rucksack einschließen oder ausschließen, aber keinen Bruchteil davon enthalten oder ihn mehrmals einschließen.

Lösung

Schritt 1:

Zuerst erstellen wir ein zweidimensionales Array (d. H. Eine Tabelle) mit n + 1 Zeilen und w + 1 Spalten.

Eine Zeilennummer i repräsentiert die Menge aller Elemente aus den Zeilen 1 bis i. Bei den Werten in Zeile 3 wird beispielsweise davon ausgegangen, dass nur die Elemente 1, 2 und 3 vorhanden sind.

Eine Spaltennummer j steht für die Tragfähigkeit unseres Rucksacks. Daher gehen die Werte in Spalte 5 beispielsweise davon aus, dass unser Rucksack 5 Gewichtseinheiten aufnehmen kann.

Wenn Sie alles zusammenfassen, stellt ein Eintrag in Zeile i, Spalte j den maximalen Wert dar, der mit den Elementen 1, 2, 3 ... i in einem Rucksack erzielt werden kann, der j Gewichtseinheiten aufnehmen kann.

Nennen wir unsere Tischmatte für Matrix. Daher ist int [] [] mat = new int [n + 1] [w + 1].

Schritt 2:

Wir können sofort damit beginnen, einige Einträge in unserer Tabelle aufzufüllen: die Basisfälle, für die die Lösung trivial ist. Zum Beispiel muss in Zeile 0, wenn wir keine Elemente zur Auswahl haben, der Maximalwert, der in einem Rucksack gespeichert werden kann, 0 sein. In Spalte 0 muss der Wert für einen Rucksack, der 0 Gewichtseinheiten enthalten kann, der Maximalwert Kann in 0 gespeichert werden. (Wir gehen davon aus, dass es keine masselosen, wertvollen Gegenstände gibt.)

Wir können dies mit 2 für Schleifen machen:

Schritt 3 (der Kern des Problems):

Nun wollen wir unseren Tisch füllen. Wie bei allen dynamischen Programmierlösungen werden wir bei jedem Schritt unsere Lösungen für frühere Unterprobleme nutzen.

Ich beschreibe zuerst die Logik, bevor ich ein konkretes Beispiel zeige.

Die Beziehung zwischen dem Wert in Zeile i, Spalte j und den Werten zu den vorherigen Unterproblemen lautet wie folgt:

Es sei daran erinnert, dass wir in Zeile i und Spalte j ein Unterproblem aus den Punkten 1, 2, 3 ... i mit einem Rucksack mit Kapazität j lösen. Zu diesem Zeitpunkt gibt es zwei Optionen: Wir können entweder Artikel I einschließen oder nicht. Daher müssen wir den maximalen Wert vergleichen, den wir mit und ohne Punkt i erzielen können.

Den maximalen Wert, den wir ohne Position i erhalten können, finden Sie in Zeile i-1, Spalte j. Dieser Teil ist einfach. Die Begründung ist unkompliziert: Unabhängig von dem maximalen Wert, den wir mit den Punkten 1, 2, 3… erzielen können, muss ich natürlich den gleichen maximalen Wert haben, den wir mit den Elementen 1, 2, 3… i - 1 erzielen können, wenn wir uns entscheiden, Artikel i nicht aufzunehmen .

Um den maximalen Wert zu berechnen, den wir mit Artikel i erzielen können, müssen wir zuerst das Gewicht von Artikel i mit der Gewichtskapazität des Rucksacks vergleichen. Wenn der Artikel i mehr wiegt als das, was der Rucksack halten kann, können wir ihn natürlich nicht einschließen. Daher ist es nicht sinnvoll, die Berechnung durchzuführen. In diesem Fall ist die Lösung dieses Problems einfach der Maximalwert, den wir ohne Punkt i erhalten können (d. H. Der Wert in der obigen Zeile in derselben Spalte).

Nehmen Sie jedoch an, dass der Artikel i weniger wiegt als die Kapazität des Rucksacks. Wir haben also die Möglichkeit, es einzubeziehen, wenn es den maximal erzielbaren Wert potenziell erhöht. Der maximal erreichbare Wert durch Einschließen von Artikel i ist somit = der Wert von Artikel i selbst + der Maximalwert, der mit der verbleibenden Kapazität des Rucksacks erzielt werden kann. Wir möchten natürlich die Kapazität unseres Rucksacks voll auslasten und keine verbleibende Kapazität verschwenden.

Daher würden wir in Zeile i und Spalte j (was den Maximalwert darstellt, den wir dort erhalten können) entweder den Maximalwert auswählen, den wir ohne Element i erhalten können, oder den Maximalwert, den wir mit Element i erhalten können, je nachdem, welcher Wert größer ist .

Hier ist ein konkretes Beispiel dafür, was ich meine.

In Zeile 3 (Punkt 2) und Spalte 5 (Rucksackkapazität von 4) können wir entweder den Punkt 2 (der 4 Einheiten wiegt) einschließen oder nicht. Wenn wir uns entscheiden, es nicht einzubeziehen, ist der maximale Wert, den wir erhalten können, derselbe, als wenn wir nur Punkt 1 zur Auswahl hätten (der sich in der obigen Zeile befindet, d. H. 0). Wenn wir Position 2 einschließen möchten, ist der Maximalwert, den wir mit Position 2 erhalten können, der Wert von Position 2 (40) + der Maximalwert, den wir mit der verbleibenden Kapazität erhalten können (die 0 ist, da der Rucksack bereits voll ist) .

In Zeile 3 (Element 2) und Spalte 10 (Rucksackkapazität von 9) können wir entweder Element 2 einschließen oder nicht. Wenn wir uns dagegen entscheiden, ist der maximale Wert, den wir erhalten können, derselbe wie der in der obigen Zeile in derselben Spalte, d. H. 10 (indem nur Punkt 1 eingeschlossen wird, der einen Wert von 10 hat). Wenn wir Punkt 2 einbeziehen, haben wir eine verbleibende Rucksackkapazität von 9 - 4 = 5. Wir können den maximalen Wert herausfinden, der mit einer Kapazität von 5 erhalten werden kann, indem Sie die Zeile oben in Spalte 5 betrachten Der Wert, den wir durch Einfügen von Punkt 2 erhalten können, ist 40 (der Wert von Punkt 2) + 10 = 50.

Wir wählen den Größeren von 50 gegen 10 aus, und der maximale Wert, den wir mit den Artikeln 1 und 2 bei einer Rucksackkapazität von 9 erreichen können, beträgt 50.

Der Algorithmus kann in Java folgendermaßen ausgedrückt werden:

Schritt 4 (Endlösung):

Nachdem die Tabelle gefüllt wurde, befindet sich die endgültige Lösung in der letzten Zeile in der letzten Spalte. Dies ist der maximale Wert, der mit allen Elementen erreicht werden kann, und die volle Kapazität des Rucksacks.

Rückmatte [n] [w];

Arbeitscode:

Hinweis: Hier habe ich die endgültige Antwort gedruckt, anstatt sie zurückzuschicken, da sich alles in einem öffentlichen statischen Hauptbereich befindet.

Danke fürs Lesen!

Siehe auch

Deligram bringt 2,5 Millionen Dollar ein, um "Mudir Dokans" für eCommerce Hubs zu gewinnen