Das Rucksackproblem (knapsack problem) ist ein modellhaftes kombinatorisches Optimierungsproblem. Aus einer Menge an Objekten, für die jeweils ein Gewicht und ein Nutzwert definiert sind, soll die optimale Kombination von Objekten zusammengestellt werden. Ziel ist die Maximierung des Wertes der ausgewählten Objekte, wobei diese Teilmenge eine vorgegebene Gewichtsschranke nicht überschreiten darf. Bildhaft übertragen besitzt man einen Rucksack mit einer maximalen Traglast (z. B. in kg) sowie eine Anzahl von Gegenständen jeweils mit Gewicht (z. B. in kg) und Wert (z. B. in Euro.) Unter Berücksichtigung der Traglast des Rucksacks soll der Wert der ausgewählten Gegenstände maximiert werden.