Skip to main content
Log in

An algorithm for the 0/1 Knapsack problem

  • Published:
Mathematical Programming Submit manuscript

Abstract

The Knapsack problem (maximize a linear function, subject to a unique constraint, all being in integers), although of thenp-complete type, is a well solved case in combinatorial programming.

The reason for this is twofold:

  1. (i)

    an upper bound of the objective function is easy to compute

  2. (ii)

    it is quite simple to construct feasible solutions. They give lower bounds of the optimum. This makes it possible to know rapidly the optimal value of many variables, and therefore to reduce the problem. Several studies have appeared recently on the subject [5, 9, 12, 18]. We present a program by which Knapsacks involving up to 60 000 boolean variables were solved in a matter of seconds, on an I.B.M. 370-168.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. E. Balas, “Discrete programming by the filter method”,Operations Research 15 (1975) 915–957.

    Google Scholar 

  2. G.H. Bradley, “Transformation of integer programs to knapsack problems”,Discrete Mathematics 1 (1) (May 1971) 29–45.

    Google Scholar 

  3. R.S. Dembro and L.H. Hammer, “A reduction algorithm for knapsack problems”, Department of Combinatorics and Optimization, Research Report CORR, University of Waterloo, Ontario, Canada (1975).

    Google Scholar 

  4. B. Faaland, “On the number of solutions to a diophantine equation”,Journal of Combinatorial Theory (A) 13 (1972) 170–175.

    Google Scholar 

  5. D. Fayard and G. Plateau, “Resolution of the 0–1 knapsack problem: Comparison of Methods”,Mathematical Programming 8 (3) (1975) 272–307.

    Google Scholar 

  6. R.S. Garfinkel and G.L. Nemhauser,Integer Programming (Wiley Interscience Publication 1972).

  7. P.C. Gilmore and R.E. Gomory, “The theory and computation of knapsack functions”,Operations Research 14 (1966) 1045–1074.

    Google Scholar 

  8. M. Gondran, “Un outil pour la programmation en nombres entiers: la méthode des congruences décroissantes”,Revue française d'Automatique Informatique, Recherche opérationnelle, Revue verte, AFCET 3 (Sept. 1973) 35–54.

    Google Scholar 

  9. H. Greenberg and R.L. Hegerich, “A branch search algorithm for the knapsack problem”,Management Science 16 (5) (1970) 327–332.

    Google Scholar 

  10. P. Hansen, “Programmes mathématiques en variables 0–1”, Thèse d'agrégation, Bruxelles, Belgique (1974).

  11. D.S. Hirschberg and C.K. Wong, “A polynomial time algorithm for the knapsack problem with two variables”,Journal of the Association for Computing Machinery 23 (1) (Jan. 1976) 147–154.

    Google Scholar 

  12. G.P. Ingargiola and J.F. Korsh, “Reduction algorithm for zero–one single knapsack problems”,Management Science 20 (4), part 1 (1973) 460–463.

    Google Scholar 

  13. P.J. Kolesar, “A branch and bound algorithm for the knapsack problem”,Management Science 13 (19) (1967) 723–735.

    Google Scholar 

  14. R. Krawczyk, “Ein Verfahren zur Lösung des bivalenten Knapsackproblems”,Angewandte Informatik 5 (1972) 223–228.

    Google Scholar 

  15. T.A. Lambe, “Bounds on the numbers of the feasible solutions to a knapsack problem”,SIAM Journal on Applied Mathematics 26 (2) (1974) 302–305.

    Google Scholar 

  16. M. Laurière, “Une méthode de résolution rapide pour le problème du knapsack”, Thèse 3ème cycle, Paris, France (1976).

  17. R.M. Nauss, “An officient algorithm for the 0–1 knapsack problem”,Management Science 23 (1) (Sept. 1976) 27–31.

    Google Scholar 

  18. S. Sahni, “Approximate algorithms for the 0–1 knapsack problem”,Journal of the Association for Computing Machinery 22 (1) (1975) 115–124.

    Google Scholar 

  19. Saunders and Schinzinger, “A shrinking boundary algorithm for discrete system models”,I.E.E., Transactions on Systems Science and Cybernetics, SSC-6 (2) (1970) 133–140.

  20. S. Martello and P. Toth, “The 0–1 Knapsacle problem”, Summer school in combinatorial optimization, Sogesta, Urbino, Instituto di Automatica, University of Bologna, Italy (May, June 1977).

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lauriere, M. An algorithm for the 0/1 Knapsack problem. Mathematical Programming 14, 1–10 (1978). https://doi.org/10.1007/BF01588947

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01588947

Key words

Navigation