So lösen Sie das Rucksackproblem mit dynamischer Programmierung

Update: Lesen Sie mehr über die Optimierung des Speicherplatzes komplexität der dynamischen Programmierlösung in meinem Follow-up-Artikel hier.,

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

„Bestimmen Sie bei einem Satz von Elementen mit jeweils einem Gewicht und einem Wert die Anzahl jedes Elements, das in eine Sammlung aufgenommen werden soll, so dass das Gesamtgewicht kleiner oder gleich einem bestimmten Limit ist und der Gesamtwert so groß wie möglich ist.“

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

Eine etwas interessantere und zuordenbarere Formulierung des 0-1-Rucksackproblems lautet:

Wenn ein Dieb in ein Haus kommt, um auszurauben, trägt er einen Rucksack. Es gibt feste Anzahl von Artikeln in der Heimat — jeder mit seinem eigenen Gewicht und Wert — Schmuck, mit weniger Gewicht und höchsten Wert vs Tabellen, mit weniger Wert, aber viel schwer. Um dem Feuer Treibstoff hinzuzufügen, hat der Dieb einen alten Rucksack mit begrenzter Kapazität., Offensichtlich kann er den Tisch nicht in zwei Hälften oder Schmuck in 3/4 teilen. Er nimmt es entweder oder verlässt es. Quelle

Leider hatte ich 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 sind in Java geschrieben. Ich werde an zusätzlichen Erklärungen und Ausarbeitungen arbeiten, wo ich sie für notwendig halte.

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

Es ist in Ordnung, wenn Sie nicht verstehen, was „optimale Unterstruktur“ und „überlappende Unterprobleme“ sind (das ist ein Artikel für einen anderen Tag). Im Wesentlichen bedeutet dies nur eine bestimmte Anzahl von Problemen, mit denen wir frühere Lösungen für kleinere Probleme wiederverwenden können, um eine Lösung für das aktuelle Problem zu berechnen. Sie werden sehen, was ich meine ein bisschen.,

Problemdetails

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

Lösung

Zuerst erstellen wir ein 2-dimensionales Array (dh eine Tabelle) von n + 1 Zeilen und w + 1 Spalten.

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

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

Alles zusammensetzen, ein Eintrag in Zeile i, Spalte j repräsentiert den Maximalwert, der mit den Elementen 1, 2, 3 … i in einem Rucksack erhalten werden kann, der j-Gewichtseinheiten aufnehmen kann.

Nennen wir unsere Tabelle mat für Matrix. Daher int mat = new int.

Schritt 2:

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

Wir können dies mit 2 for-Schleifen tun:

Schritt 3 (der Kern des Problems):

Jetzt möchten wir anfangen, unsere Tabelle zu füllen., Wie bei allen dynamischen Programmierlösungen werden wir bei jedem Schritt unsere Lösungen für frühere Teilprobleme verwenden.

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 ist wie folgt:

Denken Sie daran, dass wir in Zeile i und Spalte j ein Unterproblem angehen, das aus den Elementen 1, 2, 3 besteht … i mit einem Rucksack j Kapazität. Es gibt 2 Optionen an dieser Stelle: Wir können entweder Artikel i einschließen oder nicht., Daher müssen wir den Maximalwert vergleichen, den wir mit und ohne Punkt i erhalten können.

Der Maximalwert, den wir ohne Punkt i erhalten können, befindet sich in Zeile i-1, Spalte j. Dieser Teil ist einfach. Die Argumentation ist einfach: alles, was maximale Wert, den wir erhalten können, mit den Nummern 1, 2, 3 … ich muss natürlich die gleiche maximale Wert, den wir erhalten können, mit den Nummern 1, 2, 3 … i – 1, wenn wir Sie nicht zu zählen Artikel, den ich.

berechnen Sie die maximale Wert, den wir erhalten können, mit dem Artikel, den ich, müssen wir uns zuerst vergleichen Sie die Gewicht der Artikel, den ich mit dem Rucksack, Gewicht Kapazität., Wenn Artikel i mehr wiegt als der Rucksack, können wir ihn natürlich nicht einbeziehen, sodass es keinen Sinn macht, die Berechnung durchzuführen. In diesem Fall ist die Lösung für dieses Problem einfach der Maximalwert, den wir ohne Punkt i erhalten können (dh der Wert in der obigen Zeile in derselben Spalte).

Nehmen wir jedoch an, dass Artikel i weniger wiegt als die Kapazität des Rucksacks. Wir haben daher die Möglichkeit, es einzubeziehen, wenn es möglicherweise den maximal erreichbaren Wert erhöht., Der maximal erreichbare Wert durch Einbeziehung von Artikel i ist somit = der Wert von Artikel i selbst + der Maximalwert, der mit der verbleibenden Kapazität des Rucksacks erhalten werden kann. Wir wollen natürlich die Kapazität unseres Rucksacks voll ausschöpfen und keine Restkapazität verschwenden.

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

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