Rucksackproblem

[Gausi]

Zitat von Luckie:

Man könnte einfach einen BruteForce Algorithmus auf das Problem los lassen und alle Möglichkeiten durchprobieren. Wäre natürlich so ziemlich das uneleganteste was es gibt, dafür aber ziemlich sicher und robust.

Da das Rucksackproblem NP-vollständig ist, bleibt einem nicht wirklich was anderes übrig, wenn man die exakte Lösung haben will. (Ich gehe davon aus, dass bei "alle Möglichkeiten durchprobieren" schon gewisse Abbruchkriterein dabei sind, sodass nicht mehr dazu gepackt wird, wenn der Rucksack eh schon zu schwer ist.)

Man könnte zwar mit diversen Heuristiken rangehen, die evtl. eine Lösung finden, die (beweisbar) nur um einen gewissen Prozentsatz von der richtigen Lösung abweicht, aber das ist hier sicherlich nicht verlangt.