3-PARTITION Problem

Ich denke durch Reduktion geht es so:

Reduzierung der 2-Partition auf 3-Partition:

Sei S die ursprüngliche Menge und A seine Gesamtsumme, dann sei S '= Vereinigung ({A / 2}, S). Somit ergibt eine 3-Partition auf der Menge S 'drei Sätze X, Y, Z. Unter X, Y, Z muss einer von ihnen {A / 2} sein, sagen wir, es ist Z, dann X und Y ist eine 2-Partition. Die Zeugen der 3-Partition auf S 'sind die Zeugen der 2-Partition auf S, also 2-Partition reduziert auf 3-Partition.

Wenn dieses Problem lösbar sein soll; dann muss sum(ALL)/3 eine Ganzzahl sein. Jede Lösung muss SUM(J) + SUM(K) = SUM(I) + sum(ALL)/3 haben. Dies stellt eine Lösung für das 2-Partitions-Problem gegenüber concat(ALL, {sum(ALL)/3}) dar.

Sie sagen, Sie haben eine Implementierung mit zwei Partitionen: Verwenden Sie sie, um das Problem zu lösen. Dann (mindestens) eine der beiden Partitionen wird die Nummer sum(ALL)/3 enthalten - entferne die Nummer von dieser Partition, und du hast I gefunden. Für die andere Partition führen Sie erneut die 2-Partition aus, um J von K ; Schließlich müssen J und K in Summe gleich sein.

Bearbeiten: Diese Lösung ist wahrscheinlich falsch - die 2-Partition der verketteten Menge wird mehrere Lösungen haben (mindestens eine für jedes von I, J, K) - Wenn es jedoch andere Lösungen gibt, dann besteht die "andere Seite" möglicherweise nicht aus der Vereinigung von zweien von I, J, K und ist möglicherweise überhaupt nicht teilbar. Sie müssen wirklich denken, ich fürchte: -).

Try 2: Iteriere über das Multiset und behalte die folgende Map: R(i,j,k) :: Boolean , was die Tatsache darstellt, ob die Zahlen bis zur aktuellen Iteration eine Aufteilung in drei Multisets erlauben mit den Summen i , j , k . Das heißt, für jede R(i,j,k) und nächste Zahl n im nächsten Zustand R' gilt das R'(i+n,j,k) und R'(i,j+n,k) und R'(i,j,k+n) . Beachten Sie, dass die Komplexität (gemäß der excersize) von der Magnitude der eingegebenen Zahlen abhängt; Dies ist ein Pseudo-Polynomzeitalgorithmus. Nikitas Lösung ist konzeptuell ähnlich, aber effizienter als diese Lösung, da sie die Summe des dritten Satzes nicht verfolgt: das ist unnötig, da Sie sie trivial berechnen können.

Sie wollen wirklich Korfs kompletten Karmarkar-Karp-Algorithmus ( Ссылка ) , Ссылка ). Eine Verallgemeinerung auf drei Partitionen ist gegeben. Der Algorithmus ist angesichts der Komplexität des Problems überraschend schnell, erfordert jedoch einige Implementierungen.

Die grundlegende Idee von KK besteht darin, sicherzustellen, dass große Blöcke ähnlicher Größe in verschiedenen Partitionen erscheinen. Man gruppiert Paare von Blöcken, die dann als ein kleinerer Block der Größe behandelt werden können, der dem Unterschied in den Größen entspricht, die wie normal platziert werden können: dadurch rekursiv gelangt man zu kleinen Blöcken, die leicht zu platzieren sind. Man führt dann eine zweifarbige Darstellung der Blockgruppen durch, um sicherzustellen, dass die gegenüberliegenden Platzierungen behandelt werden. Die Erweiterung auf 3-Partition ist etwas kompliziert. Die Korf-Erweiterung soll Tiefensuche in KK-Reihenfolge verwenden, um alle möglichen Lösungen zu finden oder schnell eine Lösung zu finden.