the problem of determining which numbers from a given collection of numbers have been added together to yield a specific sum: used in cryptography to encipher (and sometimes decipher) messages.

Origin

so called because the problem is similar to determining what packages are in a closed knapsack when the weights of the individual packages and the filled knapsack are known

The functions based on the knapsack problem have unresolved problems regarding security.

knapsack problem in Technology

application, 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 0/1 knapsack problem restricts the number of each items to zero or one. Such constraint satisfaction problems are often solved using dynamic programming. The general knapsack problem is NP-hard, and this has led to attempts to use it as the basis for public-key encryption systems. Several such attempts failed because the knapsack problems they produced were in fact solvable by polynomial-time algorithms. [Are there any trusted knapsack-based public-key cryptosystems?]. (1995-04-10)