Subset-sum problems with different summands: Computation (Q922292)

Let \(A=\{a_ 1,...,a_ m\}\), \(a_ i\in N\), \(a_ i\leq l\) and let \(A^*\) be a set of subset sums, i.e., \(A^*=\{S_ B| S_ B=\sum_{a_ i\in B}a_ i\), \(B\subseteq A\}\). The subset-sum problem (SSP) can be formulated as follows: find a maximal subset sum \(S\in A^*\) such that \(S\leq M\), where M is any given positive number. The interesting paper presents two algorithms for SSP with different summands which are based on analytical results of number theory. The first one improves the time bound of one of Freiman's algorithm to O(m log m), the time bound of the second algorithm is O(m).