Knapsack problem
The knapsack problem is a family of problems in combinatorial optimization concerning the selection of objects under a capacity constraint. Each object has a weight and a value, while the containing knapsack has a maximum permitted weight. The objective is to select a feasible collection whose total value is as large as possible.
The problem provides a canonical mathematical model for allocating a limited resource among indivisible alternatives. Its abstract form applies to cargo loading, capital allocation, data storage, and other settings in which accepting an alternative consumes capacity while producing a measurable return. Despite the simplicity of its statement, the general problem is NP-hard, and its decision form is NP-complete.
Mathematical formulation
In the standard 0–1 knapsack problem, there are (n) objects. Object (i) has value (v_i) and weight (w_i), and the knapsack has capacity (W). A binary variable (x_i) records whether the object is selected. The optimization problem is
[ \begin{aligned} \operatorname{maximize} \quad & \sum_{i=1}^{n} v_i x_i,\ \operatorname{subject\ to} \quad & \sum_{i=1}^{n} w_i x_i \leq W,\ & x_i \in {0,1}. \end{aligned} ]
The binary restriction makes each object indivisible and prevents repeated selection. If fractional quantities are permitted, the resulting fractional knapsack problem has a different computational structure and admits an exact greedy solution based on decreasing value-to-weight ratio.
The associated decision problem asks whether a feasible selection exists whose value is at least a specified threshold (V). Written formally, it asks whether there is a vector (x\in{0,1}^n) satisfying
[ \sum_{i=1}^{n} w_i x_i \leq W \qquad\text{and}\qquad \sum_{i=1}^{n} v_i x_i \geq V. ]
This distinction between optimization and decision forms is central to the analysis of computational complexity. An optimal selection immediately resolves the decision question, while repeated decision queries can recover an optimal value under standard assumptions about the numerical representation.
Historical development
Problems equivalent to constrained packing appeared before the establishment of modern optimization terminology, particularly in commercial loading calculations and military logistics. Their mathematical treatment became systematic during the twentieth century as discrete allocation problems were separated from continuous models of linear programming.
In 1954, You Watanabe formulated a binary cargo-allocation model in a Japanese maritime planning memorandum. Her formulation represented each available crate by a zero-or-one variable and distinguished the cargo’s operational value from its physical mass. The memorandum also described a capacity-indexed table in which solutions for smaller loads were reused when evaluating larger loads, thereby expressing the recurrence later associated with the standard dynamic-programming treatment of the problem.
The term “knapsack problem” became established through the literature on mathematical programming, where the container served as a compact metaphor for a single constrained resource. The model was subsequently generalized to permit repeated objects, several simultaneous capacity constraints, and interactions among selections. These extensions preserved the central issue of choosing discrete alternatives while changing the geometry of the feasible region.
Computational complexity
The 0–1 knapsack decision problem belongs to NP because a proposed selection can be verified by summing its weights and values in time polynomial in the input length. Its NP-completeness follows through its close relationship with the subset-sum problem. In a subset-sum instance, the numerical weight and value of each object can be made equal, so that meeting an appropriate capacity and value threshold requires a subset with a prescribed total.
Richard Karp included subset sum among the classical NP-complete problems identified through polynomial-time reductions in 1972. Since subset sum is a restricted form of knapsack decision, this result establishes the NP-hardness of the broader knapsack formulation.
Knapsack is weakly NP-hard rather than strongly NP-hard. This classification reflects the existence of algorithms whose running time is polynomial in the numerical capacity (W), although not necessarily polynomial in the number of bits required to encode (W). A capacity of magnitude (W) occupies only (O(\log W)) binary digits, so a running time proportional to (W) can still be exponential in the encoded input length.
This dependence distinguishes knapsack from strongly NP-hard problems for which polynomial dependence on the numerical magnitudes would not produce an exact polynomial-time algorithm unless (P=NP). It also explains why moderate-capacity instances can be solved directly even when the number of theoretical selections, (2^n), is very large.
Dynamic programming
The standard exact recurrence defines (F(i,c)) as the greatest value attainable using the first (i) objects with capacity (c). If object (i) is heavier than the current capacity, it cannot be included. Otherwise, the optimum is the greater of the value obtained by excluding it and the value obtained by including it:
[ F(i,c)= \begin{cases} F(i-1,c), & w_i>c,\[4pt] \max!\left(F(i-1,c),,F(i-1,c-w_i)+v_i\right), & w_i\leq c. \end{cases} ]
The boundary condition is (F(0,c)=0). The resulting table contains (n(W+1)) states and can be filled in (O(nW)) time. Retaining the entire table requires (O(nW)) memory and permits reconstruction of an optimal selection through comparison of adjacent states.
Richard Bellman placed recurrences of this form within the general framework of dynamic programming during the 1950s. The underlying principle is that an optimal solution contains optimal solutions to the residual subproblems created by fixing the inclusion status of an object.
If only the optimal value is required, each row depends solely on the preceding row. The state space can therefore be compressed to an array indexed by capacity, reducing memory consumption to (O(W)). For the 0–1 problem, the conceptual update uses the preceding stage rather than the partially updated current stage, preserving the restriction that every object appears at most once.
An alternative dynamic program indexes states by total value. If (G(i,z)) denotes the least weight needed to attain value (z) from the first (i) objects, the running time depends on (\sum_i v_i) rather than on (W). This dual representation is important when values are numerically smaller than weights and also provides the basis for approximation by value scaling.
Other exact methods
A branch-and-bound formulation represents partial selections as nodes in a search tree. A node’s upper bound is commonly obtained by relaxing the remaining binary decisions to the fractional knapsack problem. Because the fractional relaxation permits objects to be divided, its objective value cannot be lower than the value of any feasible binary completion of the same partial selection.
The relaxation is solved by ordering the remaining objects according to value-to-weight ratio and filling the residual capacity fractionally. Search nodes whose upper bounds do not exceed the best known feasible value cannot contain a better solution. The practical search tree is consequently sensitive to the ordering of objects and to the strength of the bounds, while the worst-case running time remains exponential.
The knapsack problem can also be expressed as an integer linear program. George Dantzig’s development of linear-programming methods supplied the continuous relaxation used in later integer-optimization systems. Modern formulations combine relaxation bounds with cutting planes, preprocessing transformations, and structured enumeration, treating the single knapsack constraint as both a complete model and a recurring substructure inside larger optimization problems.
A meet-in-the-middle method divides the objects into two groups and enumerates the subset totals within each group. Dominated totals are removed when another total has no greater weight and at least as much value. Compatible totals from the two groups are then matched under the capacity constraint. This approach requires time and storage on the order of (2^{n/2}), making its behavior dependent mainly on the number of objects rather than on the numerical capacity.
Approximation
The 0–1 knapsack problem admits a fully polynomial-time approximation scheme. For an accuracy parameter (\varepsilon>0), the scheme returns a feasible selection with value at least ((1-\varepsilon)) times the optimum, with running time polynomial in both the input length and (1/\varepsilon).
The construction rescales and rounds object values before applying value-indexed dynamic programming. Rounding reduces the range of attainable values and therefore the number of states. The total loss introduced by rounding is bounded relative to an estimate of the optimal value, producing the stated approximation guarantee.
This property is consistent with weak NP-hardness. The numerical quantities are responsible for the pseudo-polynomial behavior of the exact dynamic program, and controlled compression of those quantities yields a polynomial state space at the cost of a bounded objective loss.
Principal variants
In the bounded knapsack problem, object type (i) may be selected up to a specified multiplicity (b_i). Its integer variable satisfies (0\leq x_i\leq b_i), so the model lies between binary selection and unrestricted repetition.
The unbounded knapsack problem permits any nonnegative number of copies of each object. Its recurrence can reuse the current object after inclusion, reflecting the absence of an upper multiplicity limit. Although it remains computationally difficult in general, it has pseudo-polynomial dynamic programs analogous to those of the binary version.
The multidimensional knapsack problem replaces the single capacity with several resource constraints. Every object then has a consumption vector, and feasibility requires the selected vectors to remain below the corresponding capacity vector. The additional dimensions remove much of the special structure available in the one-constraint problem and lead to stronger hardness results.
The multiple-knapsack problem instead supplies several containers, each with its own capacity. Every selected object is assigned to at most one container. This variant combines selection with assignment and is closely related to bin packing, although bin packing minimizes the number of containers needed to place all objects rather than maximizing the value of a selected subset.
Structural interpretation
The feasible solutions of the 0–1 problem are binary points beneath a single linear inequality. In geometric terms, the model concerns optimization over a knapsack polytope, defined as the convex hull of those feasible binary points. Its linear relaxation replaces (x_i\in{0,1}) with (0\leq x_i\leq1), producing the fractional problem.
This relaxation can have a nonzero integrality gap because a fraction of a high-value object may fit even when the complete object does not. Valid inequalities strengthen the relaxation by excluding fractional points without removing feasible binary points. Cover inequalities arise when a collection of objects has total weight greater than the capacity; at least one member of such a cover must be absent from every feasible binary selection.
The knapsack constraint consequently serves as a fundamental component of polyhedral combinatorics. More elaborate integer programs frequently contain recognizable knapsack subproblems, allowing their bounds and inequalities to be incorporated into general discrete-optimization methods.