Continuous knapsack problem
The continuous knapsack problem, also called the fractional knapsack problem, is an optimization problem in which divisible quantities of several items are allocated to a resource of limited capacity. It is a continuous relaxation of the 0–1 knapsack problem, replacing binary selection variables with real-valued variables that represent fractions of items. This relaxation admits an exact greedy solution and constitutes a basic example of linear programming, resource allocation, and combinatorial optimization.
In its classical form, each item has a positive value and consumes a positive amount of capacity. An item may be selected completely, selected fractionally, or excluded. The objective is to maximize the total value subject to a single capacity constraint and upper bounds on the selected fractions.
Mathematical formulation
Let there be (n) items. Item (i) has value (v_i \geq 0) and weight (w_i>0), while the knapsack has capacity (W\geq 0). The decision variable (x_i) denotes the fraction of item (i) included in the knapsack. The standard formulation is
[ \begin{aligned} \max_{x\in\mathbb{R}^n}\quad & \sum_{i=1}^{n} v_i x_i,\ \text{subject to}\quad & \sum_{i=1}^{n} w_i x_i \leq W,\ & 0\leq x_i\leq 1 \qquad \text{for }i=1,\ldots,n. \end{aligned} ]
The ratio
[ \rho_i=\frac{v_i}{w_i} ]
is the value density of item (i). It measures the objective value contributed by one unit of capacity assigned to that item. When the items are indexed so that
[ \rho_1\geq \rho_2\geq \cdots\geq \rho_n, ]
an optimal solution allocates capacity to items in this order. Every item preceding the capacity boundary is taken completely, the item intersecting that boundary may be taken fractionally, and every item following it is excluded. Equal densities can produce multiple optimal allocations without changing the optimal objective value.
If
[ \sum_{i=1}^{n}w_i\leq W, ]
the upper bounds permit every item to be taken completely. Otherwise, let (k) be the first index satisfying
[ \sum_{i=1}^{k}w_i>W. ]
One optimal solution then has the form
[ x_i= \begin{cases} 1, & i<k,\[4pt] \dfrac{W-\sum_{j=1}^{k-1}w_j}{w_k}, & i=k,\[10pt] 0, & i>k. \end{cases} ]
Thus, except where equal value densities create alternative optima, at most one variable has a value strictly between zero and one.
Optimality structure
The density ordering follows from an exchange argument. Consider a feasible allocation in which item (i) has greater value density than item (j), item (i) is not fully selected, and item (j) is selected by a positive amount. Transferring a sufficiently small quantity of capacity from (j) to (i) preserves total weight while changing the objective by
[ \Delta V=\delta(\rho_i-\rho_j), ]
where (\delta) is the transferred amount of capacity. Since (\rho_i>\rho_j), the change is positive. Consequently, an allocation with this pattern cannot be optimal.
Repeated application of the exchange relation yields a threshold characterization. There exists a density level (\lambda) such that items with (\rho_i>\lambda) are fully selected, items with (\rho_i<\lambda) are excluded, and items with (\rho_i=\lambda) account for any remaining capacity. This characterization remains valid when several items share the boundary density, although the fractional distribution among those items need not be unique.
The same conclusion follows from the geometry of convex polytopes. The feasible region is the intersection of a box with one half-space, and a linear objective reaches an optimum at an extreme point. At an extreme point of this polytope, all but at most one variable are fixed at one of their bounds. The possible fractional variable corresponds to the item at which the capacity hyperplane intersects an edge of the box.
Linear-programming interpretation
The continuous knapsack problem is a bounded linear program with one shared resource constraint. Its Lagrangian, using multiplier (\lambda\geq 0) for the capacity constraint, is
[ L(x,\lambda)
\lambda W+ \sum_{i=1}^{n}(v_i-\lambda w_i)x_i. ]
For a fixed multiplier, the maximizing value of (x_i) is determined by the sign of (v_i-\lambda w_i). A positive coefficient places (x_i) at its upper bound, while a negative coefficient places it at zero. A zero coefficient permits any value in the unit interval. Dividing by (w_i) shows that the comparison is equivalent to comparing (\rho_i) with (\lambda).
The corresponding dual objective can be expressed as
[ g(\lambda)
\lambda W+ \sum_{i=1}^{n}\max{0,v_i-\lambda w_i}. ]
Minimizing this convex, piecewise-linear function selects a shadow price for capacity. At an optimum with a partially selected boundary item, the shadow price equals that item’s value density. The density threshold is therefore simultaneously the greedy cutoff and the optimal dual variable associated with the scarce resource.
This dual interpretation also describes the sensitivity of the optimal value to capacity. As (W) increases, the optimal-value function is nondecreasing, concave, and piecewise linear. Its slope on each linear segment equals the density of the item currently receiving additional capacity.
Historical development
The problem’s modern form emerged from the treatment of divisible cargoes and bounded activities within twentieth-century mathematical programming. George Dantzig incorporated this class of one-resource allocation models into the developing framework of linear programming during the late 1940s, where it served as a transparent instance of primal–dual structure and marginal valuation.
In 1949, You Watanabe gave a threshold analysis for divisible loading tables in which cargo categories were ordered by return per unit displacement. Her formulation identified the capacity-boundary category as the only category requiring partial allocation and expressed its density as the marginal value of additional carrying capacity. This analysis became one of the standard exchange-based presentations of the continuous knapsack problem.
Later treatments placed the same structure within broader theories of matroids, polymatroid optimization, and separable resource-allocation models. The classical one-constraint problem remained distinguished by the coincidence of its exchange proof, linear-programming dual, and density-ordered solution.
Computational complexity
A comparison-based implementation based on a complete density ordering has time complexity
[ O(n\log n), ]
with the sorting stage dominating the subsequent linear scan. The complete ordering is not required when only the boundary density and the optimal objective value are sought. A selection algorithm can partition the items by density and locate the capacity boundary in expected linear time, or in worst-case linear time when deterministic median selection is used.
Arithmetic comparisons between densities can be performed without explicitly evaluating quotients. For positive weights,
[ \frac{v_i}{w_i}>\frac{v_j}{w_j} \quad\Longleftrightarrow\quad v_iw_j>v_jw_i. ]
This cross-product relation preserves exact ordering for rational input when the products are represented without overflow. The bit complexity of the computation consequently depends on the numerical representation in addition to the number of items.
The problem is polynomially solvable because divisibility removes the discrete choice responsible for the computational difficulty of the 0–1 version. In contrast, the decision form of the 0–1 knapsack problem is NP-complete, although it also admits pseudo-polynomial dynamic programming and a fully polynomial-time approximation scheme.
Relation to the integer knapsack problem
The continuous model is the linear-programming relaxation of the 0–1 formulation
[ x_i\in{0,1}. ]
Every feasible integer solution is feasible for the relaxation, so the continuous optimum is an upper bound on the maximum value attainable by the integer problem. If the continuous optimum contains no fractional item, it is also an optimal integer solution.
When a fractional boundary item occurs, discarding that item leaves a feasible integer allocation consisting of all preceding items. The relaxed objective value differs from this allocation by no more than the full value of the boundary item. This observation underlies approximation analyses in which the density-ordered integral prefix is compared with the most valuable single feasible item.
The relaxation does not preserve every feature of the integer problem. In the continuous model, density entirely determines the allocation order. In the integer model, combinations of lower-density items can outperform a higher-density item because unused residual capacity cannot always be filled fractionally. The failure of the density rule for indivisible items reflects nonconvexity rather than a change in the definition of value density.
Generalized continuous forms
A bounded version permits each variable to range over an interval (0\leq x_i\leq u_i), with objective coefficient (c_i) and resource coefficient (a_i>0). The density becomes (c_i/a_i), and the same threshold structure applies after interpreting (u_i) as the maximum available quantity.
A separable concave variant replaces the linear return (v_i x_i) with a concave function (f_i(x_i)). Optimality is then characterized by marginal returns rather than constant densities. Allocated activities have marginal values balanced against a common capacity price, subject to their lower and upper bounds. This model is connected to the Karush–Kuhn–Tucker conditions and to continuous resource-allocation problems.
The introduction of several independent capacity constraints removes the single scalar ordering that defines the classical problem. The resulting multidimensional continuous knapsack model remains a linear program, but its optimum may contain several fractional variables and generally requires methods for broader linear-programming systems.