Combinatorial properties of the bounded knapsack problem

The combinatorial properties of the set of solutions to the bounded knapsack problem are considered. As in the general case, this problem is an NP-complete combinatorial optimization problem and its exact solution requires the use of search algorithms with the decomposition of a set of feasible solutions. In this regard, the question of determining and evaluating the properties of the set of acceptable solutions to the problem is relevant. In this paper, formulas are obtained which allow to calculate the average value of the functional of a problem on the set of its feasible solutions and the power of this set through the number of solutions of subtasks of smaller dimension. The basic technique for obtaining results is the method of generating functions. We also consider the knapsack problem with arbitrary values of variables, in which the coefficients of the constraint vector and the objective function coincide. For this, the “continuity” of the set of solutions is assumed. Estimates of the values of the functional in this problem are found. The results may be of interest for the design of computational algorithms for finding and estimating the number of solutions and the value of the functional for optimal solutions. The expressions found can also be used in auxiliary procedures to evaluate the optimality of the solution in decomposition or heuristic algorithms for solving the knapsack problem.