Knapsack problem
<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?].
