The Theory and Computation of Knapsack Functions

Abstract

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 l i 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.