knapsack problem

    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)