knapsack problem

1 definition found

knapsack problem - Free On-line Dictionary of Computing (26 May 2007) :

  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)