follow Dictionary.com

It’s about time. We are now on Instagram!

knapsack problem

noun, Mathematics
1.
the problem of determining which numbers from a given collection of numbers have been added together to yield a specific sum: used in cryptography to encipher (and sometimes decipher) messages.
Origin
so called because the problem is similar to determining what packages are in a closed knapsack when the weights of the individual packages and the filled knapsack are known
Dictionary.com Unabridged
Based on the Random House Dictionary, © Random House, Inc. 2014.
Cite This Source
Examples from the web for knapsack problem
  • The functions based on the knapsack problem have unresolved problems regarding security.
knapsack problem in Technology
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?].
(1995-04-10)
The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source

Word of the Day

Difficulty index for knapsack problem

Few English speakers likely know this word

Word Value for knapsack

20
23
Scrabble Words With Friends

Nearby words for knapsack problem