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:
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 Link To knapsack problem
FOLDOC
Computing Dictionary

knapsack problem definition

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
Example sentences
The functions based on the knapsack problem have unresolved problems regarding security.
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;