Ich weiß, dass hier viel geredet wurde, aber ich kämpfe mit diesem Problem.
Wir haben eine Menge von Zahlen, z. B. [3, 1, 1, 2, 2, 1], und wir müssen sie in zwei Teilmengen aufteilen, so dass jede Summe gleich oder die Differenz minimal ist.
Ich habe Wikipedia-Eintrag gesehen, dies Seite (Problem 7) und ein Blogeintrag .
Aber jeder der aufgelisteten Algorithmen gibt nur ein JA / NEIN Ergebnis und ich verstehe wirklich nicht, wie man sie benutzt, um zwei Teilmengen auszudrucken (zB S1 = {5, 4} und S2 = {5, 3, 3}) . Was fehlt mir hier?
Der Pseudo-Polynomalgorithmus wurde entwickelt, um eine Antwort auf das Entscheidungsproblem zu liefern, nicht das Optimierungsproblem . Beachten Sie jedoch, dass die letzte Zeile in der Booleschen Tabelle in dem Beispiel angibt, dass der aktuelle Satz summierbar ist bis zu N / 2.
Nimm in der letzten Zeile die erste Spalte, in der der boolesche Wert true ist. Sie können dann überprüfen, was der tatsächliche Wert der Menge in der gegebenen Spalte ist. Wenn der summierte Wert der Sätze N / 2 ist, haben Sie den ersten Satz der Partition gefunden. Andernfalls müssen Sie prüfen, welcher Satz den Unterschied zu N / 2 ausmachen kann. Sie können den gleichen Ansatz wie oben verwenden, diesmal für den Unterschied d .
Dies ist O (2 ^ N) . Keine dynamische Programmierung wird hier verwendet. Sie können Ergebnis1, Ergebnis2 und Differenz nach Ausführung der Funktion ausdrucken. Ich hoffe, das hilft.
%Vor%Ich hatte vor kurzem dasselbe Problem und schrieb eine Frage dazu (hier: Variante des Rucksacks ). Der Unterschied in meinem Fall ist, dass die resultierenden Teilmengen die gleiche Größe haben müssen (wenn die ursprüngliche Menge eine gerade Anzahl von Elementen hat). Um das zu gewährleisten, fügte ich @Sandesh Kobal Antwort ein paar Zeilen hinzu;
%Vor% Außerdem habe ich nach beiden Aufrufen von partition if(diffsofar==0) return; hinzugefügt. Wenn wir bereits eine optimale Lösung gefunden haben, macht es keinen Sinn weiter zu suchen ...
Tags und Links algorithm