Knapsack problem

The knapsack problem ( engl. also knapsack problem) is an optimization problem in combinatorics. From a set of objects, each with a weight and a value in use, is a subset are selected whose total weight does not exceed a given weight limit. Under this condition, the utility value of the selected objects is to be maximized.

The decision variant of the knapsack problem asks whether a given user value addition can be achieved. It belongs to the list of 21 classic NP -complete problems, of which Richard Karp 1972 could show the belonging to this class.

In cryptography, a different decision variant is often considered. Only the weights are considered and it is asked whether there is a subset of the objects that reached a predetermined weight value exactly. This problem variant is also called SUBSET - SUM. Based on this variation, the public-key cryptosystems Merkle -Hellman cryptosystem has been developed, but which turned out to be not particularly safe.

View

The knapsack problem has received its name from the following intuition out: There are given different items of a certain weight and value in use. For these objects, a selection will now be made ​​, which can be carried in a backpack with a given weight limit. In the literature, like the thief is used to illustrate which may carry away in your backpack only a small part of the booty and is trying to knock out the maximum utility value.

Mathematical formulation

Is given a finite set of objects. By a weight function and the utility function is the objects associated with a weight and a value in use:

Furthermore, there is a predetermined weight limit.

Wanted is a subset of, the condition of the

Solution by dynamic programming

Are the weights integer, so can the optimal value of the knapsack problem solve by dynamic programming. Be to the elements of.

In each memory cell is the maximum value in use at a maximum possible weight in consideration of a subset of objects from the partial sequence of the complete sequence of all objects. Thus, the maximum value in use in consideration of a subset of all objects stored in the cell after completion of the algorithm.

In each row of the matrix is optimized over the two cases, if the utility can be magnified up when the object with the weight added to the backpack or it is not accepted. In the first case, the utility increased by.

To determine the contents of the backpack with the maximum ease of use, it can be reconstructed by calculating the optimum is traced in backtracking.

The correctness follows from the following observation:

Be an optimum solution. Then is an optimal solution for the instance with maximum weight. The algorithm needed due to the nested for loops that iterate over n and B, a term of. It should be noted that B represents an input to its length exponentially growing size and thus the term is pseudopolynomiell.

Applications

Many real problems can be traced back to this problem and the solution. Often there is a limited capacity available, which can not satisfy all the demand. Consider, for example, to a truck, the many different goods - with a certain profit - to transport, but can not accept any goods due to the limited amount of charge. The owner of the truck will want to choose the charge so that the profit is maximized.