das Problem, für n Objekte mit Gewichten G_i, 1 ≤ i ≤ n, Nutzenwerten N_i, 1 ≤ i ≤ n, und eine Gewichtsschranke G eine Menge von Objekten zu berechnen, die zusammen die Gewichtsschranke nicht überschreiten, also eine zumutbare Bepackung eines Rucksacks darstellen, und dabei zusammen maximalen Nutzen haben.

Die Entscheidungsvariante (Entscheidungsproblem) ist NP-vollständig, aber für jedes ε > 0 gibt es einen approximativen Algorithmus, der das Problem mit einer worst case Güte (Güte eines Algorithmus) von 1 + ε in polynomieller Zeit löst.