Search in: Word
Vietnamese keyboard: Off
Virtual keyboard: Show
Computing (FOLDOC) dictionary
knapsack problem
Jump to user comments
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
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