Computing Partitions with Applications to the Knapsack Problem

Abstract

Given $r$ numbers $s_{1}, \ldots, s_{r}$, algorithms are investigated for finding all possible combinations of these numbers which sum to $M$. This problem is a particular instance of the 0-1 unidimensional knapsack problem. All of the usual algorithms for this problem are investigated both in terms of asymptotic computing times and storage requirements, as well as average computing times. We develop a technique which improves all of the dynamic programming methods by a square root factor. Using this improvement a variety of new heuristics and improved data structures are incorporated for decreasing the average behavior of these methods. The resulting algorithms are then compared on a wide set of data. It is then shown how these improvements can be applied to various versions of the knapsack problem. Key words and Phrases: partitions, knapsack problem, dynamic programmiing, integer optimization.