Computational Methods in Discrete Mathematics

On the average number of solutions in the knapsack problem

M. S. A. Volkov^a, E. N. Gordeev^a, V. K. Leontiev<sup>b

a</sup> Bauman Moscow State Technical University, Moscow, Russia
^b Dorodnitsyn Computing Center of the Russian Academy of Sciences, Moscow, Russia

Abstract: Exact analytical expressions are derived for the average number of solutions to the bounded knapsack problem over a set of fixed-dimension instances. The average number of solutions for a set of knapsack problems with the constraint $ \sum\limits_{i = 1}^n {a_i x_i \leqslant b} $, where the coefficients $ a_i $ do not exceed a given value $ p $, is denoted as $ |\bar{V_p}| $. Formulas are obtained that relate the number of solutions to problem parameters such as the dimension $ n $, weight limit $ p $, and allowable variable values. For Boolean variables $ x_i \in \{0,1\}$, the following formula is derived:
$$ |\bar{V_b}|=\frac{1}{(b+1)^n} \textstyle\sum\limits_{k=0}^n \dbinom{n}{k} \dbinom{b}{n-k} (b+2)^k. $$
For the case $ x_i \in \{0,1,2\}$, a generalized expression is obtained:
\begin{gather*} |\bar{V_b}|{=} \textstyle\sum\limits_{k=0}^n \dbinom{n}{k} (b{+}1)^{k-n} \sum\limits_{t=0}^{n-k} \dbinom{n{-}k}{t} 2^t \Biggl( \dbinom{(n{-}k{+}t{+}b{-}1)/{2}}{n-k}\big[n{-}k{+}t{+}b {=} 1 (\bmod 2)\big] + \\ +\binom{(n-k+t+b)/{2}}{n-k}\big[n-k+t+b= 0 (\bmod 2) \big] \Biggl). \end{gather*}
Additionally, a formula is derived that defines the generating function for the volume of the set of solutions to problems of dimension $n$ with components of the weight vector $(a_1,\dots,a_n)$ taking values in the range from $0$ to $p$. The obtained results can be applied to assess the computational complexity of knapsack problem algorithms, select optimal solution methods, develop decomposition algorithms, and analyze combinatorial structures arising in discrete optimization problems.

Keywords: knapsack problem, generating functions, dynamic programming, NP-complete problems, coefficient method.

UDC: 519.16

DOI: 10.17223/20710410/68/7