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.
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 wi of material that is available to be selected and the total value vi of that material.
The goal is to choose an amount xi ≤ wi of each material, subject to the capacity constraint
In the classic knapsack problem, each of the amounts xi must be either zero or wi; the continuous knapsack problem differs by allowing xi to range continuously from zero to wi.
[1] Some formulations of this problem rescale the variables xi to be in the range from 0 to 1.
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.
[1][2] However, by adapting an algorithm for finding weighted medians, it is possible to solve the problem in time O(n).