Combinatorial optimization: Knapsack problem 1: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
| Zeile 20: | Zeile 20: | ||
[[Datei:knapsack table 1.jpg]] | [[Datei:knapsack table 1.jpg]] | ||
| + | |||
[[Datei:knapsack table 2.jpg]] | [[Datei:knapsack table 2.jpg]] | ||
Version vom 27. Juni 2013, 16:09 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
