Kennt jemand eine Möglichkeit, Zahlen gleichmäßig in eine bestimmte Anzahl von Containern zu verteilen, um sicherzustellen, dass die Gesamtwerte der Container so gleichmäßig wie möglich sind?
BEARBEITEN: Mit "so gut wie möglich" meine ich, dass die Summe jedes Containers dem Gesamtdurchschnitt so nahe kommt, wenn er in X Containern verteilt wird.
Im Moment sortiere ich einfach die Reihe der Zahlen (absteigend) und verteile sie, ohne ihren Wert zu beachten, in die Container. Ein Satz von 1000, 200, 20, 1000, verteilt auf drei Behälter, wäre gleich [2000], [200], [20].
Was ich machen möchte ist:
%Vor%Aber ich kenne keinen sauberen Weg, dies im Code auszudrücken.
Ideen?
Verfügen Sie über einen großen Datensatz mit einer großen Varianz in der Größe von Objekten und eine Gussanforderung, dass Sie müssen die beste Lösung finden? Wenn ja, ist das nicht realistisch.
Aber die gute Nachricht ist, dass viele Probleme, die in der Theorie NP-vollständig sind, in der realen Welt ziemlich einfach sind! Wenn Ihre Anzahl an Datenpunkten relativ klein ist, können Sie wahrscheinlich eine intelligente (aber immer noch gründliche) Suche durchführen und die global optimale Lösung finden.
Auch wenn die Varianz in den Werten ziemlich klein ist Wenn Sie einen gut benannten Datensatz haben, stolpern Sie möglicherweise schnell über eine Lösung, die alle Container genau gleichmäßig füllt. Wenn ja, dann ist dies offensichtlich die bestmögliche Antwort. Dies könnte auch bei sehr großen Datensätzen gut funktionieren. (Ich denke, dass Sie hier ein Dataset mit vielen kleinen Werten haben möchten, mit denen Sie am Ende alles aufräumen können.).
Also, gib nicht auf! Sortiere zuerst deine Daten und betrachte die Datenpunkte vom größten zum kleinsten. Weisen Sie in jeder Phase dem aktuell kleinsten Container den nächsten Wert zu. Dies wird wahrscheinlich nicht die optimale Lösung in allen Fällen geben, aber es könnte in der Praxis durchaus sinnvoll sein.
Wenn Sie 1000, 200, 20, 1000 sortieren, erhalten Sie 1000, 1000, 200, 20 . Dieser Algorithmus würde Ihnen dann geben:
Dies ist die optimale Lösung, aber das wird nicht immer so sein.
====
Wenn Sie willens und in der Lage sind, komplexere Algorithmen auszuprobieren, lesen Sie das Partitionsproblem :
Obwohl das Partitionsproblem NP-vollständig ist, gibt es a Pseudo-Polynom-Zeit dynamische Programmierlösung, und es gibt Heuristiken, die das Problem in vielen Fällen entweder optimal lösen oder ungefähr. Aus diesem Grund heißt es "Das Einfachste Hartes Problem ".
Es gibt eine Optimierungsversion des Partitionsproblems, das darin besteht, das Multiset S in zwei Teilmengen S1, S2 aufzuteilen, so dass die Differenz zwischen der Summe der Elemente in S1 und der Summe der Elemente in S2 minimiert wird.
Interessant. Dieses C-Programm scheint bisher das erwartete Ergebnis zu liefern. Es beginnt mit dem Sortieren der Daten und speichert dann für n -Container sofort die n höchsten Zahlen in jedem einzelnen. (Sie können diesen Schritt tatsächlich überspringen.) Dann wird von der größten verbleibenden Zahl bis zur kleinsten der Container gefunden, bei dem das Hinzufügen dieser Zahl den geringsten Unterschied zum optimalen Durchschnitt ergibt. Da dies von hoch nach niedrig verläuft, wird jede Zahl in den optimalen Container gestellt - alle anderen Zahlen sind niedriger, daher wäre der Unterschied für sie sogar größer.
%Vor%Tags und Links algorithm