Subset-sum Problem
The subset sum problem, is a special case of the decision and 0-1 problems where each kind of item, the weight equals the value: . In the field of cryptography, the term knapsack problem is often used to refer specifically to the subset sum problem and is commonly known as one of Karp's 21 NP-complete problems.
The generalization of subset-sum problem is called multiple subset-sum problem, in which multiple bins exist with the same capacity. It has been shown that the generalization does not have an FPTAS.
Read more about this topic: Knapsack Problem, Variations
Famous quotes containing the word problem:
“Consciousness is what makes the mind-body problem really intractable.”
—Thomas Nagel (b. 1938)