Opening the knapsack by DFTs
Torleiv Maseng · Electronics Letters · 1987
A new simple algorithm which uses discrete Fourier transforms for breaking the general knapsack problem (also known as the subset sum problem) is presented along with the number of operations required for solving the problem. The method is applicable when the elements belong to a Galois field as well as that of a set of integers and is most effective for high-density knapsacks.