Das Rucksackproblem in C (Knapsack problem)

5. September 2010

In den letzten Tagen habe ich mich mal wieder mit den „üblichen Verdächtigen“ in der Informatik beschäftigt. Da gibt es so eine Sammlung von immer wieder beleuchteten Problemstellungen wie die „Türme von Hanoi“ und eben auch das „Rucksackproblem“ (en. knapsack problem). Dabei geht es darum daß man einen Rucksack packen muss in den weniger hinein passt als man eigentlich gern mitnehmen würde. Also muss man sich für eine Kombination von Dingen entscheiden die den Platz im Rucksack „optimal“ ausnutzt. Und genau das tut der Algorithmus dann. Er sucht aus einer vorgegebenen Auswahl die Objekte aus die gerade so in den Rucksack passen und maximalen „Nutzen“ beinhalten. Dieses Optimierungsproblem lässt sich natürlich auf alle Probleme ausdehnen die eine knappe Resource auf Nutzer mit einem Kosten/Nutzen Faktor verteilen muss.

Den Rest des Beitrags lesen »