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.

Beispiel

Text

Varianten

Text

Tiefensuche

Breitensuche

Beschränkung des Suchbaumes

Nichtdeterminismus