Lexikon der Mathematik: Rucksackproblem
das Problem, für n Objekte mit Gewichten Gi, 1 ≤ i ≤ n, Nutzenwerten Ni, 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.
Schreiben Sie uns!