Eine Variation des Rucksackproblems: So lösen Sie das Problem der Partition Equal Subset Sum in Java

Zuvor schrieb ich über die Lösung des Knapsack-Problems (KP) mit dynamischer Programmierung. Sie können hier darüber lesen.

Heute möchte ich eine Variation von KP diskutieren: das Problem der Summe der Partitionsgleichheit. Ich habe dieses Problem zum ersten Mal bei Leetcode gesehen - dies hat mich dazu veranlasst, KP kennenzulernen und darüber zu schreiben.

Dies ist die Problemstellung (teilweise ohne Beispiele wiedergegeben):

Wenn ein nicht leeres Array nur positive Ganzzahlen enthält, prüfen Sie, ob das Array in zwei Teilmengen aufgeteilt werden kann, sodass die Summe der Elemente in beiden Teilmengen gleich ist.

Die vollständige Problembeschreibung mit Einschränkungen und Beispielen finden Sie im Leetcode-Problem.

Dynamische Programmierung

Wie bei KP werden wir dies mithilfe dynamischer Programmierung lösen. Da dies eine Variation von KP ist, sind Logik und Methodik weitgehend ähnlich.

Lösung

Wir werden unsere Lösung in einer Methode unterbringen, die einen Booleschen Wert zurückgibt - true, wenn das Array in gleiche Teilmengen aufgeteilt werden kann, andernfalls false.

Schritt 1: Schutz vor ungerader Array-Summe

Wenn sich alle Zahlen im Array zu einer ungeraden Summe addieren, können wir trivialerweise false zurückgeben. Wir fahren nur fort, wenn das Array eine gerade Summe ergibt.

Schritt 2: Erstellen der Tabelle

Als nächstes erstellen wir die Tabelle.

Tabellenzeilen stellen die Menge der zu berücksichtigenden Array-Elemente dar, während Tabellenspalten die Summe angeben, zu der wir gelangen möchten. Tabellenwerte sind einfach boolesche Werte, die angeben, ob eine Summe (Spalte) mit einer Reihe von Array-Elementen (Zeile) ermittelt werden kann.

Konkret repräsentiert Zeile i eine Menge von Array-Elementen von den Indizes 0 bis ( i -1). Der Grund für diesen Versatz von 1 ist, dass Zeile 0 eine leere Menge von Elementen darstellt. Daher repräsentiert Zeile 1 das erste Array-Element (Index 0), Zeile 2 die ersten beiden Array-Elemente (Indizes 0–1) und so weiter. Insgesamt erstellen wir n + 1Zeilen einschließlich 0.

Wir wollen nur wissen, ob wir genau die Hälfte der Gesamtsumme des Arrays zusammenfassen können. Wir müssen also nur totalSum / 2 + 1Spalten einschließlich 0 erstellen .

Schritt 3: Vorfüllen der Tabelle

Wir können sofort mit dem Ausfüllen der Einträge für die Basisfälle in unserer Tabelle beginnen - Zeile 0 und Spalte 0.

In der ersten Zeile muss jeder Eintrag - mit Ausnahme des ersten - sein false. Denken Sie daran, dass die erste Zeile eine leere Menge darstellt. Natürlich können wir keine Zielsumme - Spaltennummer - außer 0 erreichen.

In der ersten Spalte muss jeder Eintrag sein true. Wir können immer trivial zu einer Zielsumme von 0 gelangen, unabhängig von der Menge der Elemente, mit denen wir arbeiten müssen.

Schritt 4: Aufbau der Tabelle (der Kern des Problems)

Ein Eintrag in der Tabelle in Zeile i und Spalte j ist true(erreichbar), wenn eine der folgenden drei Bedingungen erfüllt ist:

  1. der Eintrag in Zeile i -1 und Spalte j ist true. Erinnern Sie sich daran, was die Zeilennummer darstellt. Wenn wir also in der Lage sind, eine bestimmte Summe mit einer Teilmenge der Elemente zu erreichen, die wir gegenwärtig haben, können wir diese Summe auch mit unserer aktuellen Menge von Elementen erreichen - indem wir einfach die zusätzlichen Elemente nicht verwenden. Das ist trivial. Nennen wir das prevRowIsTrue.
  2. Das aktuelle Element ist genau die Summe, die wir erreichen wollen. Dies ist auch trivial wahr. Nennen wir das isExactMatch.
  3. Wenn die beiden oben genannten Bedingungen nicht erfüllt sind, haben wir noch eine Möglichkeit, unsere Zielsumme zu erreichen. Hier verwenden wir das aktuelle Element - das zusätzliche Element in der Elementmenge in unserer aktuellen Zeile im Vergleich zur Elementmenge in der vorherigen Zeile - und prüfen, ob wir den Rest der Zielsumme erreichen können. Nennen wir das canArriveAtSum.

Lassen Sie uns Bedingung 3 entpacken. Wir können das aktuelle Element nur verwenden, wenn es kleiner als unsere Zielsumme ist. Wenn sie gleich sind, wäre Bedingung 2 erfüllt. Wenn es größer ist, können wir es nicht verwenden. Daher besteht der erste Schritt darin, sicherzustellen, dass das aktuelle Element <Zielsumme ist.

Nachdem wir unser aktuelles Element verwendet haben, bleibt uns der Rest unserer Zielsumme übrig. Wir prüfen dann, ob dies erreichbar ist, indem wir den entsprechenden Eintrag in der obigen Zeile überprüfen.

Wie bei regulären KP möchten wir unsere Tabelle schrittweise von unten nach oben aufbauen. Wir beginnen mit den Basisfällen, bis wir zu unserer endgültigen Lösung gelangen.

Schritt 5: Rückgabe der Antwort

Wir kehren einfach zurück return mat[nums.length][totalSum / 2].

Arbeitscode

Danke fürs Lesen!