TOPICS

# Knapsack Problem

Given a sum and a set of weights, find the weights which were used to generate the sum. The values of the weights are then encrypted in the sum. This system relies on the existence of a class of knapsack problems which can be solved trivially (those in which the weights are separated such that they can be "peeled off" one at a time using a greedy-like algorithm), and transformations which convert the trivial problem to a difficult one and vice versa. Modular multiplication is used as the trapdoor one-way function. The simple knapsack system was broken by Shamir in 1982, the Graham-Shamir system by Adleman, and the iterated knapsack by Ernie Brickell in 1984.

Coin Problem, Greedy Algorithm, Postage Stamp Problem, Subset Sum Problem, Trapdoor One-Way Function

## Explore with Wolfram|Alpha

More things to try:

## References

Coppersmith, D. "Knapsack Used in Factoring." §4.6 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 117-119, 1987.Lichtblau, D. "Solving Knapsack and Related Problems." Unpublished manuscript.Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 163-166, 1985.

Knapsack Problem

## Cite this as:

Weisstein, Eric W. "Knapsack Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/KnapsackProblem.html