An Efficient Algorithm for the 0-1 Knapsack Problem

Robert M. Nauss
Robert M. Nauss
University of Missouri-St. Louis
Search for more papers by this author

University of Missouri-St. Louis

Published Online:1 Sep 1976https://doi.org/10.1287/mnsc.23.1.27

Abstract

In this note we present an efficient algorithm for the 0-1 knapsack problem and announce the availability of a callable FORTRAN subroutine which solves this problem. Computational results show that 50 variable problems can be solved in an average of 4 milliseconds and 200 variable problems in an average of 7 milliseconds on an IBM 360/91.

Cited by
- Branch-and-Bound and Dynamic Programming Approaches for the Knapsack Problem
  17 October 2024 | Operations Research Forum, Vol. 5, No. 4
- Modified symbiotic organisms search (MSOS) algorithm for solving 0-1 Knapsack problems
  20 November 2024 | OPSEARCH, Vol. 31
- Local-search based heuristics for advertisement scheduling
  8 August 2024 | RAIRO - Operations Research, Vol. 58, No. 4
- Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties
  6 January 2023 | Optimization Letters, Vol. 17, No. 8
- Framework for selecting carbon emission abatement projects in supply chains
  1 June 2022 | Supply Chain Forum: An International Journal, Vol. 24, No. 3
- High-Dimensional Cost-constrained Regression Via Nonconvex Optimization
  4 May 2021 | Technometrics, Vol. 64, No. 1
- A Comparative Study of Meta-Heuristic Optimization Algorithms for 0 – 1 Knapsack Problem: Some Initial Results
  IEEE Access, Vol. 7
- A Binary Multi-Scale Quantum Harmonic Oscillator Algorithm for 0–1 Knapsack Problem With Genetic Operator
  IEEE Access, Vol. 7
- A modified artificial bee colony approach for the 0-1 knapsack problem
  25 August 2017 | Applied Intelligence, Vol. 48, No. 6
- Risk-Sensitive Stochastic Orienteering Problems for Trip Optimization in Urban Environments
  8 February 2018 | ACM Transactions on Intelligent Systems and Technology, Vol. 9, No. 3
- An exact approach for the 0–1 knapsack problem with setups
  Computers & Operations Research, Vol. 80
- Quantum-Inspired Evolutionary Algorithm for difficult knapsack problems
  21 April 2015 | Memetic Computing, Vol. 7, No. 2
- Combining human and machine processes (CHAMP)
- Solution of “Hard” Knapsack Instances Using Quantum Inspired Evolutionary Algorithm
- Facility Location Models
  21 October 2013
- Solution of “Hard” Knapsack Instances Using Quantum Inspired Evolutionary Algorithm
  International Journal of Applied Evolutionary Computation, Vol. 5, No. 1
- Lagrangian relaxation and pegging test for the clique partitioning problem
  30 May 2013 | Advances in Data Analysis and Classification, Vol. 7, No. 4
- Parameterized model and approach for constrained project portfolio optimization
- Adaptive Data Refinement for Parallel Dynamic Programming Applications
- A class of nonlinear nonseparable continuous knapsack and multiple-choice knapsack problems
  5 March 2009 | Mathematical Programming, Vol. 126, No. 1
- Two-person knapsack game
  Journal of Industrial & Management Optimization, Vol. 6, No. 4
- A successive approximation algorithm for the multiple knapsack problem
  17 November 2007 | Journal of Combinatorial Optimization, Vol. 17, No. 4
- Single-vendor multi-buyer inventory coordination under private information
  European Journal of Operational Research, Vol. 191, No. 2
- Methods for selecting the optimal portfolio of projects
- Design of reliable SONET feeder networks
  7 February 2007 | Information Technology and Management, Vol. 8, No. 1
- Dynamic Generalized Assignment Problems with Stochastic Demands and Multiple Agent--Task Relationships
  15 February 2016 | Journal of Global Optimization, Vol. 31, No. 1
- The elastic generalized assignment problem
  21 December 2017 | Journal of the Operational Research Society, Vol. 55, No. 12
- Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach
  Robert M. Nauss,
  1 August 2003 | INFORMS Journal on Computing, Vol. 15, No. 3
- Upper Bounds for the SPOT 5 Daily Photograph Scheduling Problem
  Journal of Combinatorial Optimization, Vol. 7, No. 1
- Supply Chain Design and Planning – Applications of Optimization Techniques for Strategic and Tactical Models
- Algorithms for Some Hard Knapsack Problems
- Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems
  European Journal of Operational Research, Vol. 125, No. 2
- New trends in exact algorithms for the 0–1 knapsack problem
  European Journal of Operational Research, Vol. 123, No. 2
- Formulating and solving production planning problems
  European Journal of Operational Research, Vol. 112, No. 1
- AN EFFICIENT APPROACH TO PRIORITIZE PROJECTS UNDER BUDGET CONSTRAINTS
  31 May 2007 | The Engineering Economist, Vol. 44, No. 3
- A Lagrangian Dual-Based Branch-and-Bound Algorithm for the Generalized Multi-Assignment Problem
  June S. Park,
  Byung Ha Lim,
  Youngho Lee,
  1 December 1998 | Management Science, Vol. 44, No. 12-part-2
- Knapsack Problems
- DGAP - The Dynamic Generalized Assignment Problem
  Annals of Operations Research, Vol. 69, No. 0
- Using Genetic Algorithms to Optimize the Selection of Cost Drivers in Activity-based Costing
  4 December 1998 | Intelligent Systems in Accounting, Finance & Management, Vol. 5, No. 3
- Optimizing single-terminal dispatch of large volume trips to trucks
  Annals of Operations Research, Vol. 50, No. 1
- File allocation involving worst case response times and link capacities: Model and solution procedure
  European Journal of Operational Research, Vol. 67, No. 3
- Videotex systems
  15 July 1992 | ACM SIGMIS Database: the DATABASE for Advances in Information Systems, Vol. 23, No. 3
- Detailed scheduling of a packing system
  The International Journal of Advanced Manufacturing Technology, Vol. 7, No. 4
- Auswahl von theoriebezogenen Veröffentlichungen
- Detailed scheduling for a class of two-stage intermittent manufacturing systems
  8 March 2007 | Production Planning & Control, Vol. 3, No. 1
- Optimal Delivery Time Quotation and Order Sequencing
  7 June 2007 | Decision Sciences, Vol. 22, No. 2
- An improved enumeration for pure 0-1 programs
  27 June 2007 | Optimization, Vol. 22, No. 2
- 3-valued problem and reduction of some integer programming problems
  Hiroshima Mathematical Journal, Vol. 21, No. 3
- Coordinated production scheduling for make-to-order manufacturing
  European Journal of Operational Research, Vol. 45, No. 2-3
- An improved direct descent algorithm for binary knapsack problems
  Computers & Operations Research, Vol. 16, No. 4
- Allocating railroad maintenance funds by solving binary knapsack problems with precedence constraints
  Transportation Research Part B: Methodological, Vol. 22, No. 3
- An integrated model of record segmentation and access path selection for databases
  Information Systems, Vol. 13, No. 1
- References
- Variablenfixierungen in gemischt-ganzzahligen linearen 0-1-Optimierungsaufgaben
  Optimization, Vol. 19, No. 5
- Comment on ‘some computational results on real 0–1 knapsack problems’
  Operations Research Letters, Vol. 6, No. 3
- A new surrogate dual multiplier search procedure
  Naval Research Logistics, Vol. 34, No. 3
- A heuristic solution procedure for the multiconstraint zero-one knapsack problem
  Naval Research Logistics, Vol. 34, No. 2
- Budgeting in Hierarchical Systems Under Uncertainty
  IIE Transactions, Vol. 19, No. 1
- Efficient algorithms for the capacitated concentrator location problem
  Computers & Operations Research, Vol. 14, No. 3
- Exact methods for the knapsack problem and its generalizations
  European Journal of Operational Research, Vol. 28, No. 1
- Algorithms for Knapsack Problems
- An integer programming model for the allocation of databases in a distributed computer system
  European Journal of Operational Research, Vol. 26, No. 3
- Some computational results on real 0–1 knapsack problems
  Operations Research Letters, Vol. 5, No. 2
- Efficient Algorithms for the Multiconstraint General Knapsack Problem
  IIE Transactions, Vol. 18, No. 2
- An efficient approximate algorithm for solving system reliability optimization problems
  22 March 2007 | Electrical Engineering in Japan, Vol. 106, No. 5
- Zero-one integer programs with few constraints —Lower bounding theory
  European Journal of Operational Research, Vol. 21, No. 2
- The zero-one knapsack problem with equality constraint
  European Journal of Operational Research, Vol. 19, No. 3
- Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
  Mathematical Programming, Vol. 31, No. 1
- Postoptimality analysis for a network protocol feature specification model
  Computers & Industrial Engineering, Vol. 9, No. 4
- Solving capacitated clustering problems
  European Journal of Operational Research, Vol. 18, No. 3
- A heuristic procedure for allocating tasks in fault‐tolerant distributed computer systems
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 30, No. 3
- An Algorithm for the Knapsack Problem
  6 July 2007 | IIE Transactions, Vol. 15, No. 1
- Comparaison de deux méthodes de résolution d'un problème combinatoire quadratique
  29 March 2011 | RAIRO - Operations Research, Vol. 17, No. 3
- Resolution of a quadratic combinatorial problem by dynamic programming
- A fully polynomial approximation algorithm for the 0–1 knapsack problem
  European Journal of Operational Research, Vol. 8, No. 3
- The Administration of Standard Length Telephone Cable Reels
- Dynamic programming algorithms for the Zero-One Knapsack Problem
  Computing, Vol. 25, No. 1
- Efficient method applying incomplete ordering for solving the binary knapsack problem
- Computational results with a branch‐and‐bound algorithm for the general knapsack problem
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 26, No. 1
- The a priori determination of optimal variable values in discrete programming problems
  USSR Computational Mathematics and Mathematical Physics, Vol. 19, No. 2
- An algorithm for the 0/1 Knapsack problem
  Mathematical Programming, Vol. 14, No. 1
- The Collapsing 0–1 Knapsack Problem
  Mathematical Programming, Vol. 15, No. 1
- An algorithm and efficient data structures for the binary knapsack problem
  European Journal of Operational Research, Vol. 2, No. 6
- A Direct Descent Binary Knapsack Algorithm
  1 April 1978 | Journal of the ACM, Vol. 25, No. 2
- Algorithm 37 Algorithm for the solution of the 0–1 single knapsack problem
  Computing, Vol. 21, No. 1
- The 0–1 knapsack problem with multiple choice constraints
  European Journal of Operational Research, Vol. 2, No. 2
- The project coordinator's problem
  Omega, Vol. 6, No. 4

Volume 23, Issue 1

September 1976

Pages 1-107

Article Information

Metrics

Information

Published Online:September 01, 1976

Cite as

Robert M. Nauss, (1976) An Efficient Algorithm for the 0-1 Knapsack Problem. Management Science 23(1):27-31.

https://doi.org/10.1287/mnsc.23.1.27

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

An Efficient Algorithm for the 0-1 Knapsack Problem

Abstract

Volume 23, Issue 1

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News