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.
Ich hatte zu der Problemstellung vor einigen Monaten einen sehr eleganten Lösungsansatz gefunden. Er wurde als Algorithmus der Woche bei der RWT Aachen vorgestellt. Vor kurzem bin ich wieder auf diesen Ansatz zurück gekommen als ich verschiedene Algorithmen implementieren musste. Nachdem ich damals keine Implementierung des Algorithmus in C gefunden hatte habe ich ihn jetzt Beispielhaft implementiert. (released into public domain). Nachdem mich nur der „Ablauf“ interessiert hatte ergibt dieser Algorithmus nur die Summengewichte. Um die Kombination der einzelnen Komponenten zu erhalten muss aber die für „payload“ verwendete Struktur erweitert werden so daß sie über die in ihrer Summe enthaltenen Komponenten Buch führt.
Nicht über die Ausgaben und Kommentare wundern, ich habe alles im Code gelassen was ich zum testen benutzt habe. Und hier ist der C Code …. :)
