Try Our Apps


WATCH "Lumbersexual"

knapsack problem

noun, Mathematics.
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 of knapsack problem
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 Unabridged
Based on the Random House Dictionary, © Random House, Inc. 2017.
Cite This Source
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?].

The Free On-line Dictionary of Computing, © Denis Howe 2010
Cite This Source

Word of the Day

Difficulty index for knapsack problem

Few English speakers likely know this word

Word Value for knapsack

Scrabble Words With Friends

Nearby words for knapsack problem