Computing Partitions with Applications to the Knapsack Problem

ABSTRACT

Given r numbers s1, ···, sr, 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

REFERENCES

• 1: BECKENBACH, E. F. (Ed). Applied Combinatorial Mathematics. Wiley, New York, 1964.
• 2: BRAI)LI.;Y, G.H. Transformation of integer programs to knapsack problems. Discrete Math 1, 1 (May 1971), 29-45.
• 3: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 4: GILMOR~.~', P. C., AND GOMORY, R. E. Multistage cutting stock problems of two and more dimensions. Oper. Res. 13 (1965), 94-120.
• 5: GILMORE, P. C., AND GOMOnY, R.E. The theory and computation of knapsack functions. Oper. Re8.14 (1966), 1045--1074.
• 6: GnE~.:NBI,:nO, H., AND HEOEmCH, R.L. A branch search algorithm for the knapsack problem. Manage. Sci. 16, 5 (Jan. 1970), 327-332.
• 7: HARDY, G. H., AND WRIGHT, E.M. A~ Introduction to the Theory of Numbers, 4th ed. Clarendon Press, Oxford, England, 1959.
• 8: INGAnGIOL~, G. P., Am) KonsH, J. F. A reduction algorithm for zero-one single knapsack problems. Manage. Sci. (to appear).
• 9: KARP, R. Reducibility among combinatorial problems. In Complexity of Computer Computa. tious, R. E. Miller and J. W. Thather, Eds., Plenum Press, N. Y., 1972, pp. 85-104.
• 10: KOLt.:SAR, P. J. A branch and bound algorithm for the knapsack problem. Manage. Sci. 13 (May 1967), 723-735.
• 11: LAWLI.:R, E. L., AND BI.:LL, M. }). A method for solving discrete optimisation problems. Oper. Res. 1,~ (1966), 1098-1112.
• 12: David Rea Musser, Algorithms for polynomial factorization., 1971
• 13: NEMHAUSI.:R, G. L., ^ND ULLMAN, Z. Discrete dynamic programming a1~d capital allocation. Manage. Sci. 15, 9 (May 1969), 494-505.
• 14: NEMHAUSl.:R, G. L., AND GARFINKEL, 1{. 17deger Programming. Wiley, New York, 1972.
• 15: W~.:I~(~ARTN{.:R, H. MARTIN, AND N~,:ss, DAWD N. Methods for the solution of the multi-dimensional 0/1 knapsack problem. Oper. Res. 15, 1 (Jan.-Feb. 1967), 83-103.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

General Terms:
Algorithms, Measurement, Performance, Theory, Verification