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)
Nearby terms:
KMODEL « KMS « kn « knapsack problem » KNI » Knights
of the Lambda-Calculus » knowbot
