Rucksackprobleme

Bei den Rucksackproblemen handelt es sich um Optimierungsprobleme. Betrachtet werden dabei nicht-leere Mengen von n Objekten.
Jedes Objekt besitzt dabei zwei Kernattribute:

• einen Wert
• ein Gewicht

Als Begrenzung dient ein fest definierter Wert, die Kapazitätsbeschränkung K.

Gesucht ist die Menge derjenigen Objekte, die in der Summe einen maximalen Wert bei bestmöglicher Ausnutzung der Kapazität haben.

Ziel

Versuch einer Lösung

Tiefensuche

Breitensuche

Beschränkung des Suchbaumes

Nichtdeterminismus