Rucksackproblem

[alzaimar]

Beim 0/1-Knapsack-Problem gibt es keine richtige Strategie. Brute-Force und Backtracking ist das einzige Verfahren, das die optimale Ergebnis liefert.

Die 'Chaos'-Suche (evoutionäre Programmierung) ist aber schon lustig:

Code:

1. Finde eine (suboptimale) Lösung (Rucksack ist  voll)
2. Nimm ein paar Dinge raus und pack ein paar wieder rein.
3. Wenn der Rucksack nun besser gepackt ist, fein. Dann haben wir eine neue (suboptimale) Lösung
4. Goto 2

Das Schöne ist, ich kann jederzeit abbrechen und habe eine i.A. brauchbare Lösung. Um dieses Verfahren allerdings sinnvoll einzusetzen, muss beim "rausnehmen und andere wieder reinpacken" ein Bookkeeping implementiert werden, um z.B. "1,2,3-raus 2,3,1 rein" zu verhindern, oder bisherige schlechtere Lösungen nochmals zu probieren.