Combinatorial optimization: Knapsack problem 2: Unterschied zwischen den Versionen
Aus Operations-Research-Wiki
[unmarkierte Version] | [unmarkierte Version] |
Zeile 19: | Zeile 19: | ||
To apply the different methods a ranking must be formed first. | To apply the different methods a ranking must be formed first. | ||
− | For this purpose, a quotient is formed from the weight a_i and the benefit c_i | + | For this purpose, a quotient is formed from the weight a_i and the benefit c_i. |
+ | Afterwards, the values are sorted according to the size. | ||
[[Datei:Quotient Liste.jpg]] | [[Datei:Quotient Liste.jpg]] | ||
+ | |||
+ | Ordered list: | ||
+ | |||
+ | [[Datei:geordnete Liste.jpg]] | ||
5. Method 4 | 5. Method 4 | ||
6. complexity problem | 6. complexity problem |
Version vom 24. Juni 2013, 14:14 Uhr
Knappsack-Problem
1. Introduction
2. Application and definition
3. Example
A woman wants to go on vacation. But now she has to overcome a serious problem, because the airline prescribe a maximum weight of 25 kg for her luggage (the worst that can happen to a woman). She has the choice between six different items which she can pack. Each object has a special benefit c_i for the woman and a weight a_i. What items should be selected by her to have the maximum benefit without exceeding the maximum weight oft 25 kg?
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
4. Methods 1 - 3
To apply the different methods a ranking must be formed first. For this purpose, a quotient is formed from the weight a_i and the benefit c_i. Afterwards, the values are sorted according to the size.
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Ordered list:
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
5. Method 4
6. complexity problem