Systematische Suche WS13-14

Aus ProgrammingWiki
< AuK
Archivierte Version vom 2013-10-08T10:46:13+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 \]$

Beispiel

Text

Varianten

Text

Tiefensuche

Breitensuche

Beschränkung des Suchbaumes

Nichtdeterminismus