Combinatorial optimization: Knapsack problem 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
| Zeile 6: | Zeile 6: | ||
A backpacker needs to choose from a bunch of items to put in his rucksack but there is not enough space for all of them as he can only carry a specific amount of weight (e.g. 30 kg). These items all have a certain value to him and a given weight. The backpacker now has to pick the items with the biggest value while staying beneath the weight limit. | A backpacker needs to choose from a bunch of items to put in his rucksack but there is not enough space for all of them as he can only carry a specific amount of weight (e.g. 30 kg). These items all have a certain value to him and a given weight. The backpacker now has to pick the items with the biggest value while staying beneath the weight limit. | ||
| − | + | '''3. Methods''' | |
| + | |||
| + | '''3.1. Kolesar''' | ||
| + | |||
Max z = ∑ cjxj | Max z = ∑ cjxj | ||
| + | |||
∑ajxj ≤ b | ∑ajxj ≤ b | ||
| + | |||
xj = 0 oder 1 | xj = 0 oder 1 | ||
| + | |||
cj = value of object j | cj = value of object j | ||
| + | |||
aj = capacity needed for object j | aj = capacity needed for object j | ||
| + | |||
b = capacity | b = capacity | ||
| − | + | [[Datei:knapsack table 1.jpg]] | |
| − | + | [[Datei:knapsack table 2.jpg]] | |
| + | [[Datei:kolesar example.jpg]] | ||
| − | + | '''3.2. Greenberg & Hegerich''' | |
| − | [[Datei: | + | [[Datei:greenberg example.jpg]] |
| + | |||
| + | '''3.3. Cascading Tree''' | ||
Version vom 27. Juni 2013, 16:15 Uhr
1. Introduction
The knapsack-problem is a problem in combinatorial optimization. The solution approach is to fill a certain object that has a given capacity limit, with items of different capacity and value. The optimal solution is the combination of items that sum up to the greatest value without crossing the capacity limit.
Originally the knapsack-problem is named after the following example: A backpacker needs to choose from a bunch of items to put in his rucksack but there is not enough space for all of them as he can only carry a specific amount of weight (e.g. 30 kg). These items all have a certain value to him and a given weight. The backpacker now has to pick the items with the biggest value while staying beneath the weight limit.
3. Methods
3.1. Kolesar
Max z = ∑ cjxj
∑ajxj ≤ b
xj = 0 oder 1
cj = value of object j
aj = capacity needed for object j
b = capacity
3.2. Greenberg & Hegerich
3.3. Cascading Tree
