Ich bin auf diese Frage gestoßen und konnte keine vernünftige Lösung finden. Wie würden Sie ein unsortiertes Integer-Array in 2 gleich große Sub-Arrays aufteilen, so dass die Differenz zwischen den Sub-Array-Summen minimal ist.
Beispiel: Bei einem Integer-Array a [N] (unsortiert) wollen wir das Array in a1 und a2 aufteilen, wobei a1.length == a2.length dh N / 2 und (Summe aller Zahlen in a1 - Summe aller Zahlen in a2) sollte minimal sein.
Nehmen wir der Einfachheit halber an, dass alle Zahlen positiv sind, aber es könnte Wiederholungen geben.
Während andere erwähnt haben, dass dies ein Fall des Partitionsproblems mit der Modifikation ist, möchte ich insbesondere darauf hinweisen, dass es sich tatsächlich um einen Spezialfall des minimales Makeup-Problem mit zwei Maschinen. Nämlich, wenn Sie das Zwei-Maschinen-Problem mit der Hauptspanne lösen und einen Wert m erhalten, erhalten Sie die minimale Differenz 2*m - sum(i : i in arr)
Wie der Wikipedia-Artikel sagt, ist das Problem für mehr als zwei Maschinen NP-vollständig. In Ihrem Fall jedoch der Listenplanungsalgorithmus , der im Allgemeinen einen ungefähre Antwort, ist optimal und polynomial-Zeit für den Zwei-Maschinen-und Drei-Maschinen-Fall gegeben eine sortierte Liste in nicht aufsteigender Reihenfolge.
Details und einige weitere theoretische Ergebnisse zu diesem Algorithmus finden Sie hier .
Tags und Links algorithm data-structures