Es gibt zwei ganzzahlige Folgen A [] und B [] der Länge N, beide unsortiert.
Voraussetzung: Durch den Austausch von Elementen zwischen A [] und B [] (kann zufällig, nicht mit dem gleichen Index) ausgetauscht werden, machen Sie den Unterschied zwischen {die Summe aller Elemente in A []} und {die Summe aller Elemente in B []} müssen minimal sein.
PS: Eigentlich ist es eine Interviewfrage, der ich begegnet bin.
Vielen Dank
Das wird NP-schwer! Ich glaube, Sie können eine Reduzierung von Subset-Summe vornehmen.
Gemäß den Kommentaren von BlueRaja / polygene werde ich versuchen, eine vollständige Reduktion von Subset Sum zu erreichen.
Hier ist eine Reduzierung:
Teilmengen-Summenproblem: Gegebene ganze Zahlen x 1, x 2, ..., x n, gibt es eine nichtleere Teilmenge was summiert sich zu Null?
Unser Problem: Bei zwei Integer-Arrays der Größe k finden Sie die kleinste mögliche Differenz der Summe der beiden Arrays, vorausgesetzt, wir können die Ganzzahlen in den Arrays mischen und beide Arrays als ein Array behandeln.
Sagen wir, wir hätten eine polynomische Zeit für unser Problem.
Sagen wir, Sie erhalten ganze Zahlen T = {x 1>, x 2, ..., x
Sei S
Sei T = {x1, x2, ..., x1-1 , x i + 1 <, ..., x
Definieren
A i = Array, das unter Verwendung von T i gebildet wird
B i = [S i, 0, ..., 0] (dh ein Element ist S i und Rest sind Nullen) ).
Sei m i = die minimale Differenz, die unser Problem für die Arrays A i und B
gefunden hat(wir führen unser Problem n mal).
Behauptung: Eine nichtleere Teilmenge von T summiert sich genau dann zu Null, wenn es ein i gibt, für das m <0 ist.
Beweis: (wlog) sagen x 1 + x <2> + .. + x
Dann
A = [x k + 1 <, ..., x
B = [x 2], x 3, ..., x k, S 1, 0, ..0]
gibt die minimale Differenz m 1 zu | x 2 + .. + x k + (x 1 + ... + x n + x 1 - (x k + 1 + + + n <) / sub>) | = | 2 (x1 + x2 + ..x k) | = 0.
Ähnlich kann der if-Teil bewiesen werden.
Tatsächlich folgt dies auch (leichter) von Partition: Erstellen Sie einfach ein neues Array mit allen Nullen.
Ich habe hoefully keine Fehler gemacht.
Nehmen Sie eine beliebige Instanz des NP-vollständigen Partitionsproblems :
Partitioniere eine Multimenge A von positiven ganzen Zahlen in zwei Multimengen B und C mit der gleichen Summe
wie {a 1 , a 2 , ..., a n }. Addiere n Nullen {0,0,0 ..., 0, a 1 , ..., a n } und frage, ob die Menge in zwei Multimengen partitioniert werden kann A und B mit der gleichen Summe und der gleichen Anzahl von Elementen. Ich behaupte, diese beiden Bedingungen sind gleichwertig:
Also, das ist eine Reduktion (also das Problem ist NP-schwer) und das Problem ist NP, also ist es NP-vollständig.
"Sequenzen A [] und B [] der Länge N" - & gt; bedeutet dies, dass sowohl A als auch B jeweils der Länge N sind?
(Aus Gründen der Übersichtlichkeit verwende ich unten 1-basierte Arrays.)
Wenn ja, wie wäre es damit:
Die Beobachtung hier ist, dass in einem sortierten Array ein benachbartes Zahlenpaar die geringste Differenz aufweist (verglichen mit einem Zahlenpaar aus nicht benachbarten Positionen). Schritt 3 stellt sicher, dass A [1] und B [1] aus einem Zahlenpaar mit dem geringstmöglichen Unterschied bestehen. Schritt 4 stellt sicher, dass (a) A [2] und B [2] aus einem Zahlenpaar mit der geringstmöglichen Differenz (aus den verfügbaren Zahlen) bestehen und auch (b) dass die Differenz in Vorzeichen von Schritt 3 entgegengesetzt ist Wenn wir so weitermachen, stellen wir sicher, dass A [i] und B [i] Zahlen mit dem geringstmöglichen Unterschied enthalten. Indem wir die Reihenfolge umkehren, in der wir Elemente an A und B senden, stellen wir sicher, dass die Differenz das Vorzeichen für jedes nachfolgende i ändert.
Ich bin mir nicht sicher, ob dies die minimal mögliche Entfernung sicherstellen wird, aber das erste, was mir in den Sinn kommt, ist etwa so:
%Vor% unter der Annahme, dass Sie eine Swap-Funktion haben, die die beiden Arrays aufnimmt und die Elemente an der Position i austauscht :)
Berechnen und Hinzufügen der Differenz zwischen den beiden Werten an der Position i erhalten Sie die inkrementelle Differenz zwischen den Summen der Elemente der beiden Arrays
Bei jedem Schritt prüfen Sie, ob es besser ist, hinzuzufügen (a [i] -b [i]) oder (b [i] -a [i]). Wenn der b [i] -a [i] der Fall ist, tauscht man die Elemente an der Position i in den Arrays aus
Vielleicht ist das nicht der beste Weg, aber es sollte ein Anfang sein:)
Das Problem ist NP-Complete.
Wir können das Partitionsproblem auf die Entscheidungsversion dieses Problems reduzieren zwei Arrays von gleich großen Ints bestimmen, ob Elemente getauscht werden können, so dass die Summen gleich sind.
Die Eingabe für das Partitionsproblem: eine Menge S von ganzen Zahlen der Größe N
Um diese Eingabe in eine Eingabe für unser Problem zu transformieren, definieren wir A als Array aller Elemente in S und B als Array derselben Größe mit B [i] = 0 für alle i. Diese Transformation ist in der Eingabegröße linear.
Es ist klar, dass unser auf A und B angewandter Algorithmus true genau dann zurückgibt, wenn es eine Aufteilung von S in 2 Teilmengen gibt, so dass die Summen gleich sind.
Tags und Links algorithm