Given $n$ elements with nonnegative integer weights $w=(w_1,\ldots,w_n)$, an integer capacity $C$ and positive integer ranges $u=(u_1,\ldots,u_n)$, we consider the counting version of the classic integer knapsack problem: find the number of distinct multisets whose weights add up to at most $C$. We give a deterministic algorithm that estimates the number of solutions to within relative error $\eps$ in time polynomial in $n, \log U$ and $1/\eps$, where $U=\max_i u_i$. More precisely, our algorithm runs in $O(\frac{n^3 \log^2 U}{\eps} \log \frac{n \log U}{\eps})$ time. This is an improvement of $n^2$ and $1/\eps$ (up to log terms) over the best known deterministic algorithm by Gopalan {\em et al.} [FOCS, (2011), pp. 817-826]. Our algorithm is relatively simple, and its analysis is rather elementary. Our results are achieved by means of a careful formulation of the problem as a dynamic program, using the notion of {\em binding constraints}.
Citation
Technical Report, Hebrew University of Jerudalem