Continuous knapsack problem

The continuous knapsack problem, also known as the fractional knapsack problem, is similar to the classic knapsack problem but in this problem fractions of an item can be put into the knapsack.

The problem is as following: Given a knapsack with capacity R and materials of different values per unit volume, find the most valuable combination of materials which fit in a knapsack of fixed volume R.

We are allowed to take fractions of materials. A greedy algorithm can find the optimum solution to the continuous knapsack problem.

This problem can arise in situation that liquid material is used. Also in Lagrangian relaxation methods for facility location problems the problem will be reduced to instances of continuous knapsack problem. Unlike knapsack problem, continuous knapsack problem is easy to solve and is sometimes used as a simplified model for the classic knapsack problem.

Solution technique

Start with the material that is most valuable per unit volume and take as much as possible until you run out. If there is still space available take the second most valuable per unit volume item and take as much as possible. Continue this procedure until you run out of room in the knapsack.

This technique was also proposed by George Dantzig as a greedy algorithm to the classic knapsack problem.