Combinatorial optimization: Knapsack problem 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
| Zeile 1: | Zeile 1: | ||
| − | + | '''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. | 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: | 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. | 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. | ||
| Zeile 11: | Zeile 13: | ||
aj = capacity needed for object j | aj = capacity needed for object j | ||
b = capacity | b = capacity | ||
| + | |||
| + | '''3. Methods''' | ||
| + | |||
| + | '''3.1. Kolesar''' | ||
| + | |||
| + | |||
| + | [[Datei:knapsack table 1.jpg]] | ||
| + | [[Datei:knapsack table 2.jpg]] | ||
Version vom 27. Juni 2013, 15:59 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.
Bedingungen: Max z = ∑ cjxj ∑ajxj ≤ b xj = 0 oder 1 cj = value of object j aj = capacity needed for object j b = capacity
3. Methods
3.1. Kolesar
