Rucksackproblem

Es beschreibt folgende Situation: Eine Person verschiedene Gegenstände. Die Gegenstände haben unterschiedliche Volumina . Die Person besitzt einen Rucksack mit einer vorgegebenen begrenzten Volumenkapazität. Kann Person den Rucksack mit einzelnen Gegenständen so dass die Summe der Gegenstände die sie Rucksack unterbringt die Volumenkapazität genau erreicht?

Formal kann die Volumenkapazität des Rucksacks <math>b \in \mathbb{N}</math> und die Einzelvolumina der verschiedenen Gegenstände als <math>a_1 ... a_k \in dargestellt werden. Eine Teilmenge der Gegenstände lässt formal als <math>I \subset \{ 1 ... \}</math> darstellen. Gesucht ist nun also ein sodass <math>\sum_{i \in I} a_i = b</math>.

Das Rucksackproblem lässt sich polynomial reduzieren auf 3-SAT und ist somit NP-vollständig .

Auf das Rucksackproblem wiederum lässt sich polynomial reduzieren.

Formulierung als Optimierungsproblem

Das Rucksackproblem kann man auch als mit Ganzzahligkeitsbedingung formulieren.

Dazu führt man die Variable x _i ein mit der Eigenschaft

• <math>x_i = 1</math> wenn man den <math>i</math> einpackt
• <math>x_i = 0</math> wenn man den <math>i</math> nicht einpackt

Dann lautet das Optimierungsproblem:

Maximiere das tatsächliche Volumen <math>V</math>

<math>V = x_1 a_1 + x_2 a_2 \dotsb + x_k a_k</math>

unter den Nebenbedingungen:

1. Das Gesamtvolumen darf <math>b</math> nicht überschreiten:

   <math>x_1 a_1 + x_2 a_2 + + x_k a_k \leq b</math>

2. Ganzzahligkeitbedingung:

   <math>x_i = 0</math> oder <math>x_i = für <math>i = 1 2 \dots k</math>

Dieses Optimierungsproblem kann man mit dem Branch and Bound lösen.

Anwendungen

Das eingangs beschriebene Rucksackproblem erscheint zunächst etwas künstliches Problem. Aber viele reale Fragestellungen sich auf dieses Problem bzw. den Lösungsansatz

Oft steht eine begrenzte Kapazität zur welche nicht die gesamte die Nachfrage befriedigen Man denke z.B. an einen LKW der verschiedene Güter - mit einem bestimmten Gewinn transportieren soll aber wegen der begrenzten Lademenge alle Güter aufnehmen kann. Der Besitzer des wird nun so die Ladung wählen dass Gewinn maximal ausfällt.

Bücher zum Thema Rucksackproblem

Dieser Artikel von Wikipedia unterliegt der GNU FDL.