The Method of Tables of Feasible Solutions for the Knapsack Problem

Abstract

The paper proposes a new approach to obtaining upper and lower bounds for the knapsack problem, which is based on the operations of ”gluing” together solutions of one layer (the k-layer is the set of solutions for which the first k components corresponding to items are defined). Two operations of gluing are considered. The first gluing operation does not lose any of the acceptable solutions, but it may appear inadmissible. Wherein, we obtain an upper bound for the solutions of the problem. In the second operation, only feasible solutions remain, but not all. In this case we obtain a lower bound for the solutions of the problem. The article presents the results of numerical experiments to estimate the time and accuracy of the proposed approach, depending on the input data size, the volume of the knapsack size and the volume of the gluing.