Fast Solution Methods for the Classical 0–1 Knapsack Problem

The classical 0-1 knapsack problem is among the simplest integer programs to state and among the most instructive problems for understanding why algorithm selection must follow instance structure. An input contains items with positive integer weights and profits, and the task is to choose a maximum-profit subset whose total weight does not exceed a capacity. The problem is weakly NP-hard, yet many large instances are solved quickly because exact algorithms exploit moderate numeric parameters, strong linear relaxations, dominance relations, or a small set of uncertain variables near the fractional break item. This review develops a theory-guided account of the principal fast solution methods for the classical problem. It proves the correctness and complexity of weight-indexed and profit-indexed dynamic programming, explains sparse Pareto-frontier implementations and reconstruction, derives the fractional-knapsack upper bound used by branch-and-bound methods, and establishes the correctness of meet-in-the-middle search. It then presents the core concept that underlies influential practical solvers and gives a detailed proof of the standard profit-scaling fully polynomial-time approximation scheme. Modern advances based on structured min-plus convolution are placed within this classical landscape rather than treated as isolated results. The central conclusion is that there is no universally fastest knapsack algorithm. Small item counts favor meet-in-the-middle search, moderate capacities or total profits favor dynamic programming, favorable density structure favors core-based exact methods, and very large numeric coefficients favor approximation. A final decision framework translates these theoretical distinctions into an implementable solver-selection policy while identifying open questions concerning adaptivity, certified switching among methods, memory efficiency, and realistic hard-instance generation.