nicht angemeldet
Hallo Cruz,
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). Es kann eben sein, dass bereits das erste Element falsch gewählt ist, dass Du in den Rucksack packst und Du damit alle Elemente wieder Rauswerfen musst.
Das Verfahren läuft in O(n^3) und ist meiner Meinung nach optimal.
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...
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.
Man kann eigentlich nur hoffen, dass das Problem klein ist oder sich mit Näherungsverfahren behelfen.
Grüße
Daniel