2
$\begingroup$

A friend of mine ask me yesterday a problem, however, the interesting part for me it is not his problem, but what I will ask here.

I want to know the optimal complexity of an algorithm (I mean the complexity of the more efficient algorithm) that solves the following problem:

Input: $n\in \mathbb N, h\in \mathbb N, (a_1,\ldots,a_n)\in \mathbb N^n.$

Output: Cardinality of the set $\{(j_1,\ldots,j_n)\in \mathbb N^n:\sum_{i=1}^n j_i a_i=h\}.$

Hope the question does make sense.

Improve this question
$\endgroup$
3
  • $\begingroup$ My guess is that depends on some kind of variance of the $(a_1,\ldots,a_n).$ For example, if all of them are equal the problem is trivial and it s getting more complicated when we start changing one then two etc... $\endgroup$
    – user39115
    Commented Oct 1, 2014 at 15:32
  • 4
    $\begingroup$ If $h$ is given in binary, the result may be exponentially large, hence you cannot do better than exponential time. If $h$ is given in unary, you can easily compute the result in polynomial time using the recurrence $S_{h,a_1,\dots,a_{n+1}}=\sum_{j\le h/a_{n+1}}S_{h-ja_{n+1},a_1,\dots,a_n}$. $\endgroup$
    – Emil Jeřábek
    Commented Oct 1, 2014 at 15:53
  • $\begingroup$ Yes, yes, it is polynomial, but, I think there is maybe an explicit formula? $\endgroup$
    – user39115
    Commented Oct 1, 2014 at 17:19

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .