Knapsack Problem

El problema de la Mochila (Knapsack Problem) es el problema clásico de optimización discreta: cada uno de los N ítems candidatos tiene un valor (vᵢ) y un peso (wᵢ), y bajo una restricción de capacidad W el objetivo es max Σvᵢxᵢ sujeto a Σwᵢxᵢ ≤ W. El nombre viene de la metáfora de llenar una mochila de capacidad limitada con la carga más valiosa. Ejemplos prácticos: selección del subconjunto de proyectos candidatos con mayor NPV bajo un presupuesto anual fijo, selección de campañas con presupuesto fijo, carga de paquetes en un avión cargo de capacidad limitada, selección de acciones small-cap en un fondo. Variantes: 0/1 (binario; xᵢ ∈ {0, 1}), bounded (xᵢ ∈ {0, ..., cᵢ}), unbounded (xᵢ ≥ 0 entero), multidimensional (MKP — m restricciones), cuadrático (QKP — sinergia por pares), multiple-choice (un ítem por grupo), subset-sum, knapsack con set-up. El knapsack es NP-hard, pero la programación dinámica de Bellman (1957) lo resuelve en O(N×W) — **pseudo-polinómico** — y con W moderado (miles a decenas de miles) maneja instancias de millones de ítems al óptimo en minutos. Branch-and-bound (Martello y Toth 1990; Pisinger 1997 expanding-core), MIP y FPTAS (Ibarra y Kim 1975 — garantía (1-ε)) son las herramientas clásicas. Referencias canónicas: Dantzig (1957) primera formulación LP/IP, Martello y Toth (1990) libro de texto, Kellerer, Pferschy y Pisinger (2004) referencia moderna completa. Portfolio Optimization (#018 Markowitz, pesos continuos más varianza) y Cutting Stock (#005, geométrico multidimensional) son parientes cercanos pero problemas distintos.