| 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 problems are often solved using . The general knapsack problem is , and this has led to attempts to use it as the basis for systems. Several such attempts failed because the knapsack problems they produced were in fact solvable by s. [Are there any trusted knapsack-based public-key cryptosystems?]. (1995-04-10) |
на заглавную 
к началу страницы