Combinatorial optimization: Knapsack problem 3: Unterschied zwischen den Versionen

Version vom 1. Juli 2013, 13:22 Uhr

1. Theory

Given an amount of objects (xj) and every object having a certain value (cj) and using a certain capacity (aj), the combinatorial optimization determines the subset of these elements with that maximize the sum of the items value under integer consideration of the variables for a given capacity limit.

In formal terms this leads to:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \max z=\sum c_{j}x_{j}

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum x_{j}a_{j}\leq b

xj = 0 or 1

cj = value of object j

aj = needed capacity of object j

b = existing capacity

The original problem was described in the process of packing a backpack (knapsack). The backpack has a certain capacity (e.g. 60 pounds) and one has to choose which things he wants to pack into the bag as all the things won´t fit in. As every item has a certain value and is using a certain capacity, one has to find the combination of items that maximizes the item´s value sum without exceeding the capacity limit of the backpack. The solution has to be integer as an item either fits in into the backpack without exceeding the capacity limit, or it does not fit in because it exceeds the capacity limit of the backpack.

2. Example

A student is facing the time in which s/he has to prepare and take exams. S/He has examined that in order to prepare properly (i.e. to pass the exam) s/he has a total time capacity of 100 preparation hours. As the student is already in 10th semester of her/his Bachelor s/he decided that s/he wants to gain as many credits as possible in the upcoming exam time. The student has some options concerning how many and which exams to write. S/He examined that s/he has a total number of 7 exams out of which s/he can choose in order to maximize the amount of credits gained in the upcoming exam period. Different exams need different preparation times and are weighted with different amounts of credits. The student also decided that the preparation time for a particular exam is either fulfilled completely or the exam is not taken at all. The ambitious student now is wondering which exams s/he should take in order to maximize the amount of credits that s/he can gain in this exam period without violating the total preparation hour’s capacity.

Can you help the student?

3. Solution

The definition of the example in formal terms is as follows:

z = credits gained in the upcoming exam period cj = credits of the exam j aj = needed preparation hours of exam j b = total preparation hours capacity (100 preparation hours) xj = the j exam

xj = 0 or 1 determines an integer solution, i.e. an exam is either taken because preparation hours can be fulfilled fully (xj =1), or an exam won´t be taken because the preparation hours aren´t fulfilled fully (xj = 0)