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.

Word History and Origins

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

Example Sentences

And the knapsack problem is more than a thought experiment.

From Fox News

Today, as technology capable of shattering the locks on our digital communications loom on the horizon, the knapsack problem may inspire new ways to prepare for that revolution.”

From Fox News

For instance, there’s one NP-complete problem called the Knapsack Problem.

From Slate

If you come up with a fast way to do the knapsack problem, you could directly apply that algorithm to the Traveling Salesman problem and vice versa.

From Slate