(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 E. Black.
Entry modified 17 December 2004.
HTML page formatted Fri Mar 25 16:20:34 2011.
Cite this as:
Paul E. Black, "fractional knapsack problem", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 17 December 2004. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/fractionalKnapsack.html
