Continuous knapsack problem
Encyclopedia
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
.
This technique was also proposed by George Dantzig
as a greedy algorithm to the classic knapsack problem
.
Knapsack problem
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as...
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
Knapsack problem
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as...
, continuous knapsack problem is easy to solve and is sometimes used as a simplified model for the classic knapsack problem
Knapsack problem
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as...
.
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
George Dantzig
George Bernard Dantzig was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics....
as a greedy algorithm to the classic knapsack problem
Knapsack problem
The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as...
.