Systematische Suche WS13-14

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2013-10-08T11:35:02+00:00. Aktuelle Version

Inhaltsverzeichnis

Autoren
Hannes Kretschmer
Julian Hilsberg

Rucksackprobleme

Aus einer Menge von Gegenständen die einen Wert w und ein Gewicht g besitzen, gilt es einen Rucksack zu füllen bei dem der Gesamtwert der eingepackten Gegenstände maximal ist, ohne die Kapizitätsgrenze K des Rucksacks zu überschreiten.

$\[ \sum_{i=1}^{n} x_i w_i \rightarrow max $ , wobei $\[ \sum_{i=1}^{n} x_i g_i \le K $, mit $ x_i \in \{0,1\} $

Allgemein beschreiben Rucksackprobleme: Beladungsprobleme, Verschnittprobleme oder Probleme der Budgetkontrolle.

Beispiel

Thomas will sein Geld anlegen und versucht ein Investment-Portfolio zu erstellen, aus dem er sich maximalen Gewinn erhofft. Er hat 10000€ (K) zur Verfügung und will diese in unterschiedliche Aktien verteilen, welche eine Bewertung (w) und einen festen zu investierenden Wert (g) besitzen. Nun geht es darum ein Portfolio zusammenzustellen (Rucksack), in welchem die Gesamtbewertung aller gekauften Aktien maximal ist, dabei darf sein Budget nicht überzogen werden.

Zur Verfügung stehende Aktien:

Aktie Mapple Minisoft
Wert 2500 1500
Bewertung (0-10, höher ist besser)/td> 8 3

Varianten

Text

Tiefensuche

Breitensuche

Beschränkung des Suchbaumes

Nichtdeterminismus