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 (b = 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

   The goal is to obtain an integer solution. One begins with the object of rank 1, then rank 2 and so on 
   and sets the variable equal 1 or 0, until the maximum weight of 25 kg is reached.
   The solution with the higher objective function value is branched. If the objective function value is less 
   than the value that provides the best integer solution, this solution is not branched.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

   b) Greenberg & Hegerich

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

   c) Cascading Tree

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

5. Method 4

6. complexity problem