Source : Free On-Line Dictionary of Computing

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)