Beweis für einen gierigen Algorithmus, der für eine Variation des Bin-Packing-Problems verwendet wird

Question

Wir erhalten ein Array von Gewichten $ W $ (alle Gewichte sind positive Ganzzahlen), und wir müssen das setzen Gewichte in den Behältern.Jeder Behälter kann maximal max_val halten, und jedes Gewicht ist höchstens max_val.Die Variation besteht darin, dass die Reihenfolge von Gewichten nicht geändert werden sollte, dh $ w_i $ sollte in einem Behälter vor $ seinW_J $ wird eingefügt, für alle $ i .

Für diese Problemanweisung können wir intuitiv sehen, dass ein gieriger Annäherungsansatz der Füllung eines Behälters bis sein Maximalwert erreicht ist, und das Erstellen eines neuen Behälters für weitere Gewichte erzeugt die Mindestanzahl der Bins.Ich kann nicht mit einem formalen Beweis kommen, dass die gierige Lösung optimal ist.Alle Hinweise oder Richtlinien wären großartig!

Answer 1

Lassen Sie $ G $ die von dem gierigen Algorithmus erzeugte Lösung sein. Für jede andere Lösung $ s $ , let $ i (s) $ Sei der Index des ersten Gewichts Zu dem der $ s $ divergiert von $ g $ . Lassen Sie $ o $ eine optimale Lösung sein, um $ I (O) $ zu maximieren. Somit $ G $ Orte $ I (O) $ in bin $ J $ (für einige $ J $ ), und $ o $ Orte < Span-Klasse="Math-Container"> $ i (o) $ in Bin $ J + 1 $ . Wenn wir $ i (o) $ in bin $ J $ (die seit $ o $ wird bestellt), erhalten wir eine Lösung $ O '$ Verwenden Sie höchstens so viele Behälter als $ o $ , und zufriedenstellend $ i (o ')> i (o) $ . Dies widerspricht der Wahl der $ o $ .

Wenn wir versuchen, dieses Argument auf dem uneingeschränkten Bin-Verpackungsalgorithmus auszuführen, haben wir Probleme beim Umzug $ i (o) $ in bin $ J $ , da dieser bin, da dieser bin möglicherweise mit anderen Elementen besetzt ist, nicht genug Platz für $ i (o) $ . In der Variante, die Sie betrachten, kann dies nicht passieren.