Knapsack problem

From Wikipedia, the free encyclopedia

Example of a one-dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to 15 kg? A multi dimensional problem could consider the density or dimensions of the boxes, the latter a typical packing problem.
(The solution in this case is to choose three yellow boxes and three grey boxes.)

The knapsack problem is a problem in combinatorial optimization. It derives its name from the following maximization problem of the best choice of essentials that can fit into one bag to be carried on a trip. Given a set of items, each with a cost and a value, determine the number of each item to include in a collection so that the total cost is less than a given limit and the total value is as large as possible.

A similar problem often appears in business, combinatorics, complexity theory, cryptography and applied mathematics.

The decision problem form of the knapsack problem is the question "can a value of at least V be achieved without exceeding the cost C?"

1 Definition
2 Dynamic programming solution
3 Greedy approximation algorithm
4 See also
5 References
6 Further reading
7 External links

[edit] Definition

In the following, we have $n$ kinds of items, 1 through $n$ . Each item $j$ has a value $p j$ and a weight $w j$ . The maximum weight that we can carry in the bag is $c$ .

The 0-1 knapsack is a special case of the original knapsack problem in which each item of input cannot be subdivided to fill a container in which that input partially fits.

The 0-1 knapsack problem restricts the number of each kind of item, $x j$ , to zero or one.

Mathematically the 0-1-knapsack problem can be formulated as:

maximize $\sum_{j=1}^n p_j x_j.$

subject to $\sum_{j=1}^n w_j x_j \le c, \quad \quad x_j = 0\;\mbox{or}\;1, \quad j=1,\dots,n.$

The bounded knapsack problem restricts the number of each item to a specific value.

Mathematically the bounded knapsack problem can be formulated as:

maximize $\sum_{j=1}^n p_j x_j.$

subject to $\sum_{j=1}^n w_j x_j \le c, \quad \quad 0 \le x_j \le b_j, \quad j=1,\dots,n.$

The unbounded knapsack problem places no bounds on the number of each item.

Of particular interest is the special case of the problem with these properties:

It is a decision problem
It is a 0/1 problem
For each item, the cost equals the value: C = V

Notice that in this special case, the problem is equivalent to this: given a set of integers, does any subset of it add up to exactly C? Or, if negative costs are allowed and C is chosen to be zero, the problem is: given a set of integers, does any subset add up to exactly 0? This special case is called the subset sum problem. In the field of cryptography the term knapsack problem is often used to refer specifically to the subset sum problem.^{[citation needed]}

The knapsack problem is often solved using dynamic programming, though no polynomial-time algorithm is known for the general problem. Both the general knapsack problem and the subset sum problem are NP-hard, and this has led to attempts to use subset sum as the basis for public key cryptography systems, such as Merkle-Hellman. These attempts typically used some group other than the integers. Merkle-Hellman and several similar algorithms were later broken, because the particular subset sum problems they produced were in fact solvable by polynomial-time algorithms.

The decision version of the knapsack problem described above ("can a value of at least V be achieved without exceeding the cost C?") is NP-complete. The subset-sum version of the knapsack problem is commonly known as one of Karp's 21 NP-complete problems.

[edit] Dynamic programming solution

The knapsack problem can be solved in pseudo-polynomial time using dynamic programming. The following depicts a dynamic programming solution for the unbounded knapsack problem.

Let the costs be c₁, ..., c_n and the corresponding values v₁, ..., v_n. We wish to maximize total value subject to the constraint that total cost is less than or equal to C. Then for each i ≤ C, define A(i) to be the maximum value that can be attained with total cost less than or equal to i. A(C) then is the solution to the problem.

Observe that A(i) has the following properties:

A(0) = 0
A(i) = max { v_j + A(i − c_j) | c_j ≤ i }.

Here the maximum of the empty set is taken to be zero. Tabulating the results from A(0) up through A(C) gives the solution. Since the calculation of each A(i) involves examining n items (all of which have been previously computed), and there are C values of A(i) to calculate, the running time of the dynamic programming solution is thus O(nC).

This does not contradict the fact that the knapsack problem is NP-complete, since C, unlike n, is not polynomial in the length of the input to the problem. The length of the input to the problem is proportional to the number of bits in C, not to C itself.

A similar dynamic programming solution for the 0-1 knapsack problem also runs in pseudo-polynomial time. As above, let the costs be c₁, ..., c_n and the corresponding values v₁, ..., v_n. We wish to maximize total value subject to the constraint that total cost is less than C. Define a recursive function, A(i, j) to be the maximum value that can be attained with cost less than or equal to j using items up to i.

We can define A(i,j) recursively as follows:

A(0, j) = 0
A(i, 0) = 0
A(i, j) = A(i - 1, j) if c_i > j
A(i, j) = max(A(i - 1, j), v_i + A(i - 1, j - c_i)) if c_i ≤ j.

The solution can then be found by calculating A(n, C). To do this efficiently we can use a table to store previous computations. This solution will therefore run in O(nC) time and O(nC) space, though with some slight modifications we can reduce the space complexity to O(C).

[edit] Greedy approximation algorithm

George Dantzig (1957) proposed a greedy approximation algorithm to solve the knapsack problem. His version sorts the essentials in decreasing order and then proceeds to insert them into the sack, starting from the first element (the greatest) until there is no longer space in the sack for more. If k is the maximum value of items that fit into the sack, the greedy algorithm is guaranteed to achieve at least a value of k/2.

[edit] See also

Branch and bound - a method applicable to n-dimensional knapsack problems
List of knapsack problems
Packing problem
Bin packing problem
Cutting stock problem

[edit] References

This article does not cite any references or sources. (June 2008)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

[edit] Further reading

Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A6: MP9, pg.247.
Silvano Martello; Paolo Toth (1990). Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons. ISBN 0-471-92420-2.
Kellerer, Hans; U. Pferschy, D. Pisinger (2005). Knapsack Problems. Springer Verlag. ISBN 3-540-40286-1.