Backpack problem

The rucksack problem: Which of the weights can be packed into the rucksack with a maximum load of 15 kg, so that the monetary value is maximized? (Solution in this case: pack all weights except the heaviest.)

The knapsack problem (also English knapsack trouble ) is an optimization problem of combinatorics . From a set of objects, each of which has a weight and a utility value , a subset is to be selected whose total weight does not exceed a specified weight limit. Under this condition, the utility of the selected objects should be maximized.

The decision variant of the rucksack problem asks whether an additional predetermined utility value can be achieved. It belongs to the list of 21 classic NP-complete problems , of which Richard Karp was able to show that they belong to this class in 1972.

In cryptography another decision variant is often considered. Only the weights are considered and a question is asked whether there is a subset of the objects that exactly reaches a specified weight value. This variant of the problem is also known as SUBSET-SUM . The Merkle-Hellman cryptosystem was developed based on this variant, although it turned out to be not particularly secure.

Intuition

The backpack problem got its name from the following point of view: There are different objects with a certain weight and a utility value. A selection is now to be made from these objects which can be taken along in a backpack with a predetermined weight limit. In the literature, the thief is often used for illustration purposes, who can only carry away a small part of the loot in a backpack and is now trying to get the maximum benefit.

Mathematical formulation

A finite set of objects is given . A weight function and the utility function assign a weight and a defined utility value to the objects: ${\ displaystyle U}$ ${\ displaystyle w}$ ${\ displaystyle v}$

{\ displaystyle w \ colon U \ rightarrow \ mathbb {R}}

{\ displaystyle v \ colon U \ rightarrow \ mathbb {R}}

There is also a specified weight limit . ${\ displaystyle B \ in \ mathbb {R}}$

We are looking for a subset that meets the condition ${\ displaystyle K \ subseteq U}$

{\ displaystyle \ sum _ {u \ in K} w (u) \ leq B}

adheres to and maximizes the objective function .

{\ displaystyle \ sum _ {u \ in K} v (u)}

The special case leads to the subtotal problem . ${\ displaystyle v = w}$

Solution by means of dynamic programming

If the weights are integers, the optimal value of the backpack problem can also be solved using dynamic programming . To do this, be the elements of . ${\ displaystyle 1, \ ldots, n}$ ${\ displaystyle U}$

1 Eingabe: U, B, w, v wie oben beschrieben
2   R := [1…(n+1), 0…B]-Matrix, mit Einträgen 0
3   FOR i = n … 1
4     FOR j = 1 … B
5       IF w(i) <= j
6         R[i,j] := max( v(i) + R[i+1, j-w(i)], R[i+1,j] )
7       ELSE
8         R[i,j] := R[i+1,j]
9 Ausgabe: R[1,B]

In each storage cell , the maximum useful value with the maximum possible total weight is, taking into account a subset of objects from the partial sequence, of the total sequence of all objects . So the maximum utility value, taking into account a subset of all objects, is stored in the cell after the algorithm has ended. ${\ displaystyle R (i, j)}$ ${\ displaystyle j}$ ${\ displaystyle [i..n]}$ ${\ displaystyle [1..n]}$ ${\ displaystyle R (1, B)}$

In each row of the matrix , the two cases are used to optimize whether the utility value can be maximally increased if the object with the weight is added to the backpack or if it is not picked up. In the first case, the utility increases by . ${\ displaystyle i}$ ${\ displaystyle R}$ ${\ displaystyle i}$ ${\ displaystyle w (i)}$ ${\ displaystyle v (i)}$

In order to determine the content of the backpack with the maximum utility value, it can be reconstructed by backtracking the calculation of the optimum using backtracking . ${\ displaystyle R (1, B)}$

The correctness follows from the following observation:

Be an optimal solution. Then there is an optimal solution for the instance with maximum weight . Due to the nested for loops that iterate over n and B, the algorithm requires a running time of . It should be noted here that B is a variable that grows exponentially in relation to its input length, and thus the running time is pseudopolynomial . ${\ displaystyle K ^ {\ star}}$ ${\ displaystyle K ^ {\ star} \ backslash \ {i \}}$ ${\ displaystyle U \ backslash \ {i \}}$ ${\ displaystyle Bw (i)}$ ${\ displaystyle O (n \ cdot B)}$

Solution using profitability index

In practice, the properties are ranked according to the profitability index :

${\ displaystyle PI = W \ div R}$

PI = profitability index
W = generated value (here: utility value)
R = consumed resources (here: weight)

Then as many properties as possible are selected, starting with the property with the highest profitability index. In the case of integer problems, this does not always lead to the optimal solution, but it is very practical. This methodology is a greedy algorithm.

Applications

Many real situations can be solved mathematically with the help of the solution to this problem. Often a limited capacity is available, which cannot meet the entire demand. Think e.g. For example, a truck that is supposed to transport many different goods - with a certain profit - but cannot take all goods due to the limited load. The owner of the truck will want to choose the load so that the profit is maximized.

literature

Hans Kellerer, Ulrich Pferschy, David Pisinger: Knapsack Problems . Springer, Berlin et al. 2004, ISBN 3-540-40286-1 .
Silvano Martello, Paolo Toth: Knapsack problems. Algorithms and computer implementations . J. Wiley, Chichester et al. 1990, ISBN 0-471-92420-2 ( book as PDF and Fortran source text for the book ).

Web links

The knapsack problem - detailed explanation with graphics and example implementation
Teaching material The backpack problem . Teacher online; Lesson about the backpack problem