Paul C. Gilmore1, Ralph E. Gomory1
1International Business Machines Corporation, Yorktown Heights, New York
Tóm tắt
In earlier papers on the cutting stock problem we indicated the desirability of developing fast methods for computing knapsack functions. A one-dimensional knapsack function is defined by: [Formula: see text] where Πi and li are given constants, i = 1, …, m. Two-dimensional knapsack functions can also be defined. In this paper we give a characterization of knapsack functions and then use the characterization to develop more efficient methods of computation. For one-dimensional knapsack functions we describe certain periodic properties and give computational results.
