On Combinatorial Properties of the Knapsack Problem

Аннотация

The knapsack problem with Boolean variables and a single constraint is studied. In the general case, this problem is NP-hard; for this reason, its exact solution requires the use of various search algorithms with the decomposition of the set of feasible solutions and computation of estimates of the objective function. Combinatorial formulas for computing and estimating the value of the objective function in various cases depending on the set of given parameters of the problem are derived. The case when the coefficients of the constraint vector coincide with the coefficients of the objective function is considered. The relationship between the set of solutions of the problem and threshold functions of a certain type is revealed. The coefficients of the objective function, the coefficients of the constraint vector, and the knapsack size are used as parameters. The classical method of generating functions is used as the basic technique. The results obtained in this paper can be used, in particular, for estimating the complexity of search and decomposition methods of solving the problem and for developing such methods as auxiliary procedures.