Computing Partitions with Applications to the Knapsack Problem

TLDR

Algorithms for finding all combinations of r numbers that sum to M, a specific case of the 0‑1 unidimensional knapsack problem, are investigated. The study develops a technique that improves dynamic programming methods by a square‑root factor and demonstrates how this improvement extends to the general 0‑1 knapsack problem, yielding a square‑root asymptotic improvement. The authors analyze all standard algorithms for the problem, evaluating asymptotic and average computing times and storage needs, and introduce a square‑root improvement to dynamic programming methods. Empirical studies show the new algorithm to outperform all previously known algorithms, and a faster branch‑and‑search method surpasses the Greenberg and Hegerich algorithm, with extensive comparative results presented.

Abstract

Given r numbers s 1 , …, 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 in terms of both 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. Empirical studies indicate this new algorithm to be generally superior to all previously known algorithms. We then show how this improvement can be incorporated into the more general 0-1 knapsack problem obtaining a square root improvement in the asymptotic behavior. A new branch and search algorithm that is significantly faster than the Greenberg and Hegerich algorithm is also presented. The results of extensive empirical studies comparing these knapsack algorithms are given