The knapsack problem (KP) appears in many forms in science, economics, and engineering. The classical formulation uses a set of items, each with a weight and a value, and asks to determine the number of each item to include in a knapsack so that the total weight is less than or equal to its limit and the total revenue is as large as possible.

The formulation of KP considered by Halman, in this paper, is not considered the revenue optimization. More exactly, the author has obtained a deterministic fully polynomial-time approximation scheme for counting the number of integer knapsack solutions of the problem: “Given n elements with non-negative integer weights w =(w1, ..., wn), an integer capacity C and positive integer ranges u =(u1, ..., un), [...] find the number of distinct multisets whose weights add up to at most C.”

According to the author, the reported result is an improvement of n2 over the best-known deterministic algorithm proposed by Gopalan [1]. Halman has proved that the running time of the algorithm depends on n (cubic polynomial class), the logarithm of the sum of upper limits ui, and the reciprocal of the relative error.

The following concepts and tools were introduced in the second section to fulfill the aim of research: k-approximation sets and functions, and binding constraints based dynamic programming (DP) approaches (primal and dual). Two algorithms based on binding constraints are given: the first one, described in the second section, is based on the primal version of DP, while the second algorithm, developed and analyzed, in the third section is based on the dual version of DP. In the fourth section, the open problems are outlined.

The paper describes valuable results on the knapsack counting problem in a clear manner, with an excellent structure and relevant and recent references.