Combinatorial optimization: Knapsack problem 1

Einführung: 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