Dictionary De - En
De - Es
De - Pt| English Dictionary: knapsack problem | by the DICT Development Group |
| 1 result for knapsack problem | |
| From The Free On-line Dictionary of Computing (15Feb98) [foldoc]: | |
|
knapsack problem 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) | |
