Modification of the Lagarias–Odlyzhko method for solving the generalized knapsack problem and the systems of knapsack problems

In 1985, to solve the computational knapsack problem, J. C. Lagarias and A. M. Odlyzhko have offered a method based on the reduction of this problem to the search of one of the short vector in the lattice of a special kind. This way allows to solve “almost all” knapsack problems that have a low density. In this paper the Lagarias–Odlyzhko method is modified to be applicable for solving the generalized knapsack problem and the systems of generalized knapsack problems. The system of knapsack problems is introduced hear as the finite set of the individual knapsack problems that have a common solution. Besides, for the generalized knapsack problem and for the systems of knapsack problems, some sets of density values are defined so that the modified methods allow to solve “almost all” generalized knapsack problems and the systems of knapsacks problems with the densities from these sets.