How to check whether a positive integer can be written as linear combination of given others, where all coefficients are positive? Let $n$, $k$ and $m_1, \dots, m_k$ be positive integers. Which is the most efficient
algorithm to find out whether there are positive integers $a_1, \dots, a_k$ such that
$n = \sum_{i=1}^k a_i m_i$?
To make things nontrivial, think of $k$ being in the hundreds, and of $n$ and the $m_i$
having hundreds of decimal digits, each. --
Clearly if we would remove the requirement that the $a_i$ are positive, the
Chinese Remainder Theorem would tell us the answer -- but we do require them to be
positive.
 A: The problem can be thought of as a coin problem. There are $k$ coins with denominations $m_1,\dots,m_k$ and you want to express an amount $n$ with these coins. As states, the problem is an integer programming question which is NP-complete when $k$ is part of the input. It is in P (with exponential dependence on $k$) when $k$ is fixed by an algorithm by Lenstra.
The problem is closely related the Frobenius/Sylvester coin problem - to find the minimum $n$ so that every larger integer has such a representation. See here and here.  A polynomial algorithm when $k$ is bounded was achieved by Ravi Kannan. (The dependence on $k$ is double-exponential.) 
These two problems (finding a representation for fixed $n$ and finding the value of $n$ above which a representation always exists) represent the first two levels in Presburger Hierarchy. An  important  open  problem  here  is  to find a P-algorithm for higher order problems in the Presburger Hierarchy. 
Of course, another important question is how to solve such questions in practice. I suppose other people can answer that better than me. One method that certainly comes to mind is to consider the linear programming relaxation (i.e. to allow rational $a_i$s) and then apply some rounding and "local" improvement.
The range proposed by the OP where $k$ - (the number of coins)  is in the hunderds is interesting. I don't know if current algorithms can scratch this value. 
