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 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 all of the boxes besides the green one.)

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. Image File history File links No higher resolution available. ... Image File history File links No higher resolution available. ... Packing problems are one area where mathematics meets puzzles (recreational mathematics). ... Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ...

A similar problem often appears in business, combinatorics, complexity theory, cryptography and applied mathematics. Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. ... As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ... Applied mathematics is a branch of mathematics that concerns itself with the mathematical techniques typically used in the application of mathematical knowledge to other domains. ...

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?" In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...

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 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

subject to

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

Mathematically the bounded knapsack problem can be formulated as:

maximize

subject to

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. For some reason, it is traditional in cryptography to say "knapsack problem" when it is actually the "subset sum problem" that is meant.^{[citation needed]} The subset sum problem is an important problem in complexity theory and cryptography. ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ...

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. In mathematics and computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods. ... In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... Public key cryptography is a form of cryptography which generally allows users to communicate securely without having prior access to a shared secret key, by using a pair of cryptographic keys, designated as public key and private key, which are related mathematically. ... Merkle-Hellman (MH) was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978. ... This picture illustrates how the hours on a clock form a group under modular addition. ... In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...

The decision version of the knapsack problem described above is NP-complete and is in fact one of Karp's 21 NP-complete problems. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... One of the most important results of computational complexity theory was Stephen Cooks 1971 paper that demonstrated the first NP-complete problem, the boolean satisfiability problem. ...

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. In computational complexity theory, pseudo-polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size n and an additional property of the input k. ... In mathematics and computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods. ...

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. Clearly, A(C) is the solution to the problem.

Define A(i) recursively as follows:

• 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. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

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. In computational complexity theory, pseudo-polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size n and an additional property of the input k. ...

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).

Greedy approximation algorithm

George Dantzig (1957) proposed a greedy approximation algorithm to solve the knapsack problem. Their 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. George Bernard Dantzig (8 November 1914 – 13 May 2005) was a mathematician who introduced the simplex algorithm and is considered the Father of linear programming. He was the recipient of many honors, including the National Medal of Science in 1975, the John von Neumann Theory Prize in 1974. ... The greedy algorithm determines the minimum number of US coins to give while making change. ... In computer science, approximation algorithms are an approach to attacking NP-hard optimization problems. ...

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

Branch and bound is a general algorithmic method for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. ... The knapsack problem is one of the most studied problems in combinatorial optimization, with many real-life applications. ... Packing problems are one area where mathematics meets puzzles (recreational mathematics). ... In computational complexity theory, the bin packing problem is a combinatorial NP-hard problem. ... The cutting stock problem arises from many physical applications in industry. ...

External links

• Lecture slides on the knapsack problem

References

• 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. 

Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NP-completeness. ... David S. Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. ...