nicht angemeldet
Hallo Kopfkratzer,
a-stangen = je 50 Meter (unbegrenzt vorhanden)
b-stangen = 5,10,15,3,21,45,33,14,26,2,1,33,28,19,7,9,10 Meter
in all dem Vorschlagssalat in diesem Thread ist meiner Meinung nach das 0-1-Rucksackproblem der richtige, den ich noch etwas ergänzen möchte. Betrachte jede a-Stange als einen einzelnen Rucksack und pack sie mit einem Greedy Ansatz der Reihe nach mit kleinen Stangen voll. Ganz konkret:
Pack einen optimalen Rucksack der Größe a aus allen verfügbaren b-Stangen und entferne die b-Stangen, die in den Rucksack gekommen sind. Wiederhole diesen Schritt, bis keine b-Stangen mehr verfügbar sind.
Das Verfahren läuft in O(n^3) und ist meiner Meinung nach optimal. Ich grübele noch an dem Beweis bzw. Gegenbeispiel.
Gruß,
Cruz