Encyclopedia > Knapsack problem

  Article Content

Knapsack problem

The knapsack problem is a problem in complexity theory, cryptography, and applied mathematics. 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 some given cost and the total value is as large as possible. The name derives from the scenario of choosing treasures to stuff into your knapsack, when you can only carry so much weight.

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

The 0/1 knapsack problem restricts the number of each items to zero or one.

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.

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 subset sum problems they produced were in fact solvable by polynomial-time algorithms.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
242

... century Decades: 190s 200s 210s 220s 230s - 240s - 250s 260s 270s 280s 290s Years: 237 238 239 240 241 - 242 - 243 244 245 246 247 Events Patriarch Titus[?] ...

 
 
 
This page was created in 66.6 ms