General technique to find largest number that can't be written as a sum of multiples of a given list of numbers

Question

I am given a set of numbers $(n_1, n_2, ...)$ with $n_1 < n_2 < ...$ and I want to know what the largest number is that can't be written as $a_1*n_1 + a_2*n_2 + ...$ The set of numbers is always finite and all $n_i$ and $a_i$ are positive integers. Is there a general technique to do this, or do you just have to try until you get $n_1$ consecutive numbers?

Answer 1

We want to assume, as the Comments note, that the GCD of values $n_i$ is 1, as otherwise there is no upper bound on numbers that cannot be represented.

Solving this, the Frobenius coin problem, has previously been discussed here.

Edit: Technically this Question differs from the Coin Problem by requiring the count $a_i$ of each denomination $n_i$ to be "positive", where these coefficients are allowed to be zero in the Coin Problem. Whether or not this was a miswording of the Question, the only effect is to add $n_1 + n_2 + \ldots$ to each possible sum, so the set of representable values is simply shifted upward by this amount.

For general cardinality of $\{n_i\}$, stipulated to be finite, the problem is NP-hard as noted in an on-line paper by D. Beihoffer et al that discusses speed of algorithms. However for fixed number of integers $n_i > 0$ there are algorithms of polynomial complexity in size of input (logarithms of $n_i$'s).