Combinatorial optimization: Knapsack problem 2

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

   This list is the basis for all applicable methods.

---

   a) Kolesar

   b) Greenberg & Hegerich

   c) Cascading Tree

5. Method 4

6. complexity problem