An Efficient Algorithm for the 0-1 Knapsack Problem
Robert M. Nauss · Management Science · 1976
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 124 works. doi:10.1287/mnsc.23.1.27
Authors
References
- Integer programming
- Lagrangian Relaxation for Integer Programming
- Computing Partitions with Applications to the Knapsack Problem
- Integer Programming Algorithms: A Framework and State-of-the-Art Survey
- A branch and bound algorithm for the generalized assignment problem
- Reduction Algorithm for Zero-One Single Knapsack Problems
- A Branch Search Algorithm for the Knapsack Problem
- Parametric Integer Programming