Knapsack problem: Difference between revisions
Content deleted Content added
imported from FOLDOC |
Larry_Sanger (talk) mNo edit summary |
||
| Line 1: | Line 1: | ||
The '''knapsack problem''' is problem in [[applied mathmatics]]. 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 '''knapsack problem''' is a problem in [[applied mathmatics]]. 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. |
||
Revision as of 23:53, 8 January 2002
The knapsack problem is a problem in applied mathmatics. 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.
Based on material from FOLDOC, used with permission.