Hallo Daniel,

Pack einen optimalen Rucksack der Größe a aus allen verfügbaren b-Stangen

Dieser Schritt mit einem Greedy-Verfahren ist in O(2^n).

Mit Greedy schon, aber mit der dynamischen Programmierung, ein Verfahren das Hand in Hand mit dem Rucksackproblem gelehrt wird, lässt sich ein Rucksack in O(n^2) packen. Wir haben maximal n viele Rucksäcke zu packen, daraus ergibt sich eine Laufzeit in O(n^3).

Der Greedy Anteil meines Vorschlag war nicht das packen eines einzelenen Rucksacks, sondern der Ansatz, dass man stets versucht jeden einzelnen Rucksack so voll wie möglich zu packen.

Optimal ist es wohl, nur ist es leider nicht in O(n^3). Das wäre auch bei einem Problem, dessen Entscheidungsvariante NP-Hart ist, eher überraschend...

Nein es ist nicht NP-Hart. Der Rucksack Problem ist nicht NP-Hart, weil es sich mit dynamischer Programmierung in polynomieller Zeit lösen lässt.

Man kann das Problem sicher auf ein Rucksack-Problem zurückführen, nur hat man damit die Problemstellung analysiert, aber noch keine Lösung gefunden.

Mein erstes Posting enthielt einen Algorithmus, der das Problem durch wiederholtes Anwenden eines Rucksack Lösers eine vollständige Lösung errechnet.

Viele Grüße,
Cruz