Systematische Suche SS10

Autoren:
Daniel Horbach
Richard Hettmann

Rucksackproblem

Das Rucksackproblem ist ein Optimierungsproblem der Kombinatorik. Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Wert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Wert der ausgewählten Objekte maximiert werden. Zur Veranschaulichung dieses klassischen Problems wird auch gerne der Dieb herangezogen, der nur einen kleinen Teil der Beute im Rucksack abtransportieren kann und nun versucht, den größtmöglichen Wert herauszuschlagen.

Grundsätzliches

Gegeben sei eine nichtleere Menge von n Gegenständen, von denen jeder einen Wert w_i und ein Gewicht g_i. Da unser Rucksack nicht unbegrenzt belastbar ist, brauchen wir noch die Aufnahmekapazität K, welche keinesfalls durch das aktuelle Gesamtgewicht überschritten werden darf.

Unser Ziel ist es nun, den Rucksack so zu füllen, dass die Wertsumme der eingepackten Gegenstände maximal ist und die Aufnamekapazität nicht überschrittn wird.

Man unterscheidet diese zwei grundsätzlich veschiedenen Arten von Rucksackproblemen:

Bruchteilrucksackproblem

Ein beliebiger Teil t eines jeden Gegenstandes darf eingepackt werden t , 0 \% <= t <= 100 \%

0/1 Rucksackproblem

Jeder einzelne Gegenstand wird entweder vollständig (1) oder garnicht (0) in den Rucksack aufgenommen