By Letter: Non-alphabet | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
  Email this page to a friend

Knapsack problem

<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 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?].

< Previous Terms Terms Containing knapsack problem Next Terms >
kluge around
0/1 knapsack problem
knapsack problem
public-key encryption
Knights of the Lambda-Calculus
Knowbot Information Service

Web Standards & Support:

Link to and support Powered by LoadedWeb Web Hosting
Valid XHTML 1.0!Valid CSS! FireFox Extensions