from
The Free On-line Dictionary of Computing (8 July 2008)
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?].
(1995-04-10)