Combinatorial optimization: Knapsack problem 2: Unterschied zwischen den Versionen
| [unmarkierte Version] | [unmarkierte Version] |
| Zeile 1: | Zeile 1: | ||
| − | ' | + | The Knapsack-problem is an optimization problem, where a quantity of objects with corresponding weights and benefits is given. The aim is to choose a subset of these objects such that the total weight doesn't exceed a given threshold and the total benefit is maximal. This Problem is also called "backpack-problem" since it results from an example in which a hiker has to pack his backpack. He has to answer the question: how can I fill the 50 liter space of the backpack to get an optimal benefit. |
| − | + | == Application and Definition == | |
| − | + | ||
| − | + | == Example == | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
A woman wants to go on vacation. But now she has to overcome a serious problem, because the airline prescribe | A woman wants to go on vacation. But now she has to overcome a serious problem, because the airline prescribe | ||
| Zeile 35: | Zeile 13: | ||
[[Datei:Tabelle Wiki.jpg]] | [[Datei:Tabelle Wiki.jpg]] | ||
| − | + | == Solution methods == | |
To apply the different methods a ranking must be formed first. | To apply the different methods a ranking must be formed first. | ||
| Zeile 52: | Zeile 30: | ||
---- | ---- | ||
| − | + | === Kolesar === | |
The goal is to obtain an integer solution. One begins with the object of rank 1, then rank 2 and so on | The goal is to obtain an integer solution. One begins with the object of rank 1, then rank 2 and so on | ||
| Zeile 62: | Zeile 40: | ||
[[Datei:Kolesar.jpg]] | [[Datei:Kolesar.jpg]] | ||
| − | + | === Greenberg & Hegerich === | |
In this method, one starts with the non-integer variable and set this variable equal 0 and 1 respectively to look | In this method, one starts with the non-integer variable and set this variable equal 0 and 1 respectively to look | ||
| Zeile 70: | Zeile 48: | ||
[[Datei:Greenberg.jpg]] | [[Datei:Greenberg.jpg]] | ||
| − | + | === Cascading Tree === | |
[[Datei:Cascading Tree.jpg]] | [[Datei:Cascading Tree.jpg]] | ||
| − | + | === Dynamic Programming === | |
| − | + | == Complexity == | |
Version vom 29. Juni 2013, 16:46 Uhr
The Knapsack-problem is an optimization problem, where a quantity of objects with corresponding weights and benefits is given. The aim is to choose a subset of these objects such that the total weight doesn't exceed a given threshold and the total benefit is maximal. This Problem is also called "backpack-problem" since it results from an example in which a hiker has to pack his backpack. He has to answer the question: how can I fill the 50 liter space of the backpack to get an optimal benefit.
Inhaltsverzeichnis
Application and Definition
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 of 25 kg?
Solution methods
To apply the different methods a ranking must be formed first.
For this purpose, a quotient is formed from the benefit c_i and the weight a_i. Afterwards, the values are sorted according to the size.
Ordered list:
This list is the basis for all applicable methods.
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. The items can be taken as long as the maximum weight of 25 kg is reached. This means that the last possible item mostly can't be taken completely. 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.
Greenberg & Hegerich
In this method, one starts with the non-integer variable and set this variable equal 0 and 1 respectively to look for a better solution. This should be continued until an optimal solution is found. The procedure is identical to the first presented method.
