Glossar · approach
Knapsack Problem
Das grundlegende diskrete Optimierungsproblem, aus N Objekten mit je einem Wert und einem Gewicht eine Teilmenge auszuwählen, die den Gesamtwert unter einer Kapazitätsschranke maximiert.
RucksackproblemKnapsack Problem0/1 KnapsackBinäres RucksackproblemMulti-Dimensional KnapsackMKP
Das Knapsack-Problem (Rucksackproblem) ist das klassische diskrete Optimierungsproblem: jedes der N Kandidatenobjekte hat einen Wert (vᵢ) und ein Gewicht (wᵢ), und unter einer Kapazitätsschranke W ist max Σvᵢxᵢ unter Σwᵢxᵢ ≤ W zu lösen. Der Name kommt aus der Metapher, einen kapazitätsbeschränkten Rucksack mit der wertvollsten Last zu füllen. Praktische Beispiele: Auswahl der NPV-höchsten Teilmenge an Kandidatenprojekten unter festem Jahres-Investitionsbudget, Kampagnenauswahl bei festem Marketingbudget, Beladung eines kapazitätsbeschränkten Cargo-Flugzeugs, Small-Cap-Aktienauswahl. Varianten: 0/1 (binär; xᵢ ∈ {0, 1}), bounded (xᵢ ∈ {0, ..., cᵢ}), unbounded (xᵢ ≥ 0 ganzzahlig), multidimensional (MKP — m Restriktionen), quadratisch (QKP — paarweise Synergie), Multiple-Choice (ein Objekt pro Gruppe), Subset-Sum, Knapsack mit Set-Up. Knapsack ist NP-hart, aber Bellmans (1957) dynamische Programmierung löst es in O(N×W) Zeit — **pseudo-polynomiell** — und bewältigt bei moderater W (Tausende bis Zehntausende) Instanzen mit Millionen Objekten zum Optimum in Minuten. Branch-and-Bound (Martello und Toth 1990; Pisinger 1997 Expanding Core), MIP und FPTAS (Ibarra und Kim 1975 — (1-ε)-Garantie) sind die klassischen Lösungswerkzeuge. Kanonische Quellen: Dantzig (1957) erste LP/IP-Formulierung, Martello und Toth (1990) Lehrbuch, Kellerer, Pferschy und Pisinger (2004) moderne umfassende Referenz. Portfolio-Optimierung (#018 Markowitz, stetige Gewichte plus Varianz) und Cutting Stock (#005, mehrdimensional geometrisch) sind enge Verwandte, aber andere Probleme.
Örnek
Das CFO-Office einer mittelständischen Holding löst ein 0/1-Knapsack-MIP über 120 Kandidatenprojekte unter 200M TRY Jahresbudget; der Gesamt-NPV der gewählten Teilmenge liegt 8% höher als bei einem Greedy 'nach NPV/Investitionsquote sortiert', weil drei kleine, hoch-rentable Projekte nun in das letzte TRY des Budgets passen.