(classic problem)
Definition: Given materials of different values per unit volume and maximum amounts, find the most valuable mix of materials which fit in a knapsack of fixed volume. Since we may take pieces (fractions) of materials, a greedy algorithm finds the optimum. Take as much as possible of the material that is most valuable per unit volume. If there is still room, take as much as possible of the next most valuable material. Continue until the knapsack is full.
Also known as continuous knapsack problem.
See also knapsack problem, unbounded knapsack problem.
Note: The problem may equivalently be expressed in terms of weight instead of volume. This is also known as the continuous knapsack problem since amounts have continuous, rather than discrete, values.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 17 December 2004.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "fractional knapsack problem", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 December 2004. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/fractionalKnapsack.html