Gewicht Balancer Algorithmus

Question

Problem

eine Liste von Elementen mit unterschiedlichen Gewichten und einer bestimmten Menge an Containern gegeben, dass die Gewichte in gespeichert werden können, die Lösungsmenge finden, die die Gewichte in den Behältern ausgleicht. Die optimale Lösung minimiert die Unterschiede zwischen dem Behälter mit dem größten Gewicht und dem Behälter mit dem geringsten Gewicht.

Kriterien

• die Alle Gewichte müssen
• Die Gewichte verwendet werden können, nicht in getrennte Behälter

Anwendung

Die eigentliche Anwendung dieses Algorithmus unterteilt werden ist es zu versuchen, einen Zeitplan in einem realen auszugleichen Zeit Betriebssystem. Die Gewichtungen sind die Laufzeit jeder geplanten Funktion und die Container sind die Rahmen, in denen die Funktionen ausgeführt werden können. Auf diese Weise versuchen Sie, die Laufzeit jeder Funktion zu verteilen, um die Gesamtrahmenzeit zu minimieren.

Gedanken

Dies scheint eine Kreuzung zwischen einer 1/0 mehr Knapsackproblems und dem Bin Packing Problem. Ich versuche, einen Algorithmus zu entwickeln, der dynamische Programmierung verwendet, um das Problem zu lösen. Ich kämpfe um zu sehen, wie ich es für dieses Problem verwenden könnte. Hat jemand Vorschläge oder Material zu ähnlichen Problemen?

Answer 1

Sie können einen Greedy-Algorithmus verwenden. Nimm die Gewichte nach dem Zufallsprinzip und füge sie dem Behälter mit dem geringsten Gewicht hinzu. Wiederholen Sie den Vorgang, bis Sie keine bessere Lösung finden, nachdem n Algorithmus ausgeführt wird.