JavaScript is disabled for your browser. Some features of this site may not work without it.
Computing Partitions with Applications to the Knapsack Problem

Author
Horowitz, Ellis; Sahni, Sartaj
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.
Date Issued
1972-07Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR72-134
Type
technical report