Knapsack Problem

Il problema dello Zaino (Knapsack Problem) è il problema classico di ottimizzazione discreta: ognuno degli N elementi candidati ha un valore (vᵢ) e un peso (wᵢ), e sotto un vincolo di capacità W l'obiettivo è max Σvᵢxᵢ soggetto a Σwᵢxᵢ ≤ W. Il nome viene dalla metafora di riempire uno zaino di capacità limitata con il carico più prezioso. Esempi pratici: selezione del sottoinsieme di progetti candidati con il più alto NPV sotto un budget annuale fisso, selezione di campagne con budget fisso, carico di colli in un aereo cargo a capacità limitata, selezione di azioni small-cap in un fondo. Varianti: 0/1 (binario; xᵢ ∈ {0, 1}), bounded (xᵢ ∈ {0, ..., cᵢ}), unbounded (xᵢ ≥ 0 intero), multidimensionale (MKP — m vincoli), quadratico (QKP — sinergia a coppie), multiple-choice (un elemento per gruppo), subset-sum, knapsack con set-up. Lo knapsack è NP-hard, ma la programmazione dinamica di Bellman (1957) lo risolve in O(N×W) — **pseudo-polinomiale** — e con W moderato (migliaia o decine di migliaia) gestisce istanze di milioni di elementi all'ottimo in minuti. Branch-and-bound (Martello e Toth 1990; Pisinger 1997 expanding-core), MIP e FPTAS (Ibarra e Kim 1975 — garanzia (1-ε)) sono gli strumenti classici. Riferimenti canonici: Dantzig (1957) prima formulazione LP/IP, Martello e Toth (1990) libro di testo, Kellerer, Pferschy e Pisinger (2004) riferimento moderno completo. Portfolio Optimization (#018 Markowitz, pesi continui più varianza) e Cutting Stock (#005, geometrico multidimensionale) sono parenti stretti ma problemi distinti.