Knapsack Problem

The Knapsack Problem is the classical discrete-optimisation problem: each of N candidate items has a value (vᵢ) and a weight (wᵢ), and under a capacity constraint W the goal is max Σvᵢxᵢ subject to Σwᵢxᵢ ≤ W. The name comes from the metaphor of packing the most valuable load into a capacity-bounded knapsack. Practical instances: selecting the subset of candidate projects with the highest NPV under a fixed annual capital budget, selecting campaigns under a fixed marketing budget, loading parcels into a capacity-bounded cargo plane, selecting small-cap stocks for a fund. Variants: 0/1 (binary; xᵢ ∈ {0, 1}), bounded (xᵢ ∈ {0, ..., cᵢ}), unbounded (xᵢ ≥ 0 integer), multi-dimensional (MKP — m constraints), quadratic (QKP — pairwise synergy), multiple-choice (one item per group), subset-sum, knapsack with set-up. The knapsack is NP-hard, but Bellman's (1957) dynamic programming solves it in O(N×W) time — **pseudo-polynomial** — and at moderate W (thousands to tens of thousands) handles million-item-scale instances to optimum in minutes. Branch-and-bound (Martello and Toth 1990; Pisinger 1997 expanding-core), MIP, and FPTAS (Ibarra and Kim 1975 — (1-ε) guarantee) are the classical solution tools. Canonical references: Dantzig (1957) for the first LP/IP framing, Martello and Toth (1990) for the textbook, Kellerer, Pferschy and Pisinger (2004) for the modern comprehensive reference. Portfolio Optimisation (#018 Markowitz, continuous weights plus variance) and Cutting Stock (#005, multi-dimensional geometric) are close relatives but distinct problems.