Lecture Notes in Computer Science
Publication date:
1987-01-01
Volume:
304
Pages:
109 -
115
Publisher:
Springer-Verlag
Author:
Jorissen, F
Vandewalle, Joos ; Govaerts, René ; Chaum, David ; Price, Wyn L
Keywords:
cosic, Science & Technology, Technology, Computer Science, Software Engineering, Computer Science, Theory & Methods, Computer Science
Abstract:
© 1988, Springer-Verlag Berlin Heidelberg. A knapsack (or subset-sum) problem that is useful for cryptographic purposes, consists of a set of n positive integers a = {a1, a2,.. an}, called the knapsack a, and a sum s. The density d of a knapsack is defined to be n /log2 (ai)max. The knapsack problem then consists of finding the set, if any, of binary numbers x = {x1, x2,.., xn}, such that Σxi·ai = s.