In theoretical computer science, the continuous knapsack problem (also known as the fractional knapsack problem) is an algorithmic problem in combinatorial optimization in which the goal is to fill a container (the "knapsack") with fractional amounts of different materials chosen to maximize the value of the selected materials.^[1][2] It resembles the classic knapsack problem, in which the items to be placed in the container are indivisible; however, the continuous knapsack problem may be solved in polynomial time whereas the classic knapsack problem is NP-hard.^[1] It is a classic example of how a seemingly small change in the formulation of a problem can have a large impact on its computational complexity.

Problem definition

An instance of either the continuous or classic knapsack problems may be specified by the numerical capacity W of the knapsack, together with a collection of materials, each of which has two numbers associated with it: the weight w_i of material that is available to be selected and the total value v_i of that material. The goal is to choose an amount x_i ≤ w_i of each material, subject to the capacity constraint

$${\displaystyle \sum _{i}x_{i}\leq W}$$

and maximizing the total benefit

$${\displaystyle \sum _{i}x_{i}v_{i}.}$$

In the classic knapsack problem, each of the amounts x_i must be either zero or w_i; the continuous knapsack problem differs by allowing x_i to range continuously from zero to w_i.^[1]

Some formulations of this problem rescale the variables x_i to be in the range from 0 to 1. In this case the capacity constraint becomes

$${\displaystyle \sum _{i}x_{i}w_{i}\leq W,}$$

and the goal is to maximize the total benefit

$${\displaystyle \sum _{i}x_{i}v_{i}.}$$

Solution technique

The continuous knapsack problem may be solved by a greedy algorithm, first published in 1957 by George Dantzig,^[2][3] that considers the materials in sorted order by their values per unit weight. For each material, the amount x_i is chosen to be as large as possible:

• If the sum of the choices made so far equals the capacity W, then the algorithm sets x_i = 0.
• If the difference d between the sum of the choices made so far and W is smaller than w_i, then the algorithm sets x_i = d.
• In the remaining case, the algorithm chooses x_i = w_i.

Because of the need to sort the materials, this algorithm takes time O(n log n) on inputs with n materials.^[1][2] However, by adapting an algorithm for finding weighted medians, it is possible to solve the problem in time O(n).^[2]

References