Direkt zum Inhalt

Lexikon der Mathematik: Rucksackproblem

das Problem, für n Objekte mit Gewichten Gi, 1 ≤ in, Nutzenwerten Ni, 1 ≤ in, 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.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos