Systematische Suche SS09
Inhaltsverzeichnis |
Systematische Suche
Rucksackprobleme
Stellen Sie sich vor, Sie wollen von einem Ort A zu einem Ort B kommen und haben für diesen Weg einen Rucksack dabei, damit Sie verschiedene Gegenstände, welche ein Gewicht und einen Wert haben transportieren wollen. Das Problem ist, dass der Rucksack nur eine Gesamtkapazität hat, die nicht überschritten werden darf. Die Aufgabe besteht nun darin, den Rucksack so zu füllen, dass die Wertsumme der eingepackten Gegenstände, unter Beachtung seiner Kapazitätsschranke, maximal ist.
Man unterscheidet dabei in zwei Formen:
- der Gegenstand wird vollständig eingepackt oder nicht
- der Gegenstand wird teilweise eingepackt
Wir betrachten nur die erste Form, dass der Gegenstand vollständig oder gar nicht eingepackt wird.
Betrachten wir das Ganze mal mathematisch :
Es gibt verschiedene Gegenstände x_i , mit einem bestimmten Gewicht g_i und einem Wert w_i . Dazu kommt dann die Kapazität des Rucksacks K .
Die Optimierungsaufgabe ist die maximale Wertsumme bei Nichtüberschreitung der Kapazitätsbeschränkung: \sum \limits _{i =1}^n {x_i w_i} \to max , wobei \sum \limits _{i =1}^n {x_i g_i} \leq K , mit x_i \in \{0,1\}