Non-negative solution to linear equation in $n$ variables Given a positive integer y and n positive integers x1 , x2 , ... , xn does there exist non negative integers a1 , a2 , ... , an such that:    
$$y = a_1 x_1 + a_2 x_2 + \dots + a_n x_n$$
The problem is just to answer if such ai's exist or not. 

My approach was to check for a given y if either of (y - xi) for i in [1..n] is expressible as a linear combination of xi's recursively and base case being that all xi's are expressible. But this approach is too slow for large values of y.

Is there some alternate faster approach?  
 A: This reminds me of the subset sum problem, which happens to be NP-Complete. It's also related to the Knapsack Problem, which, given your problem statement, seems to fit quite nicely. 
As the Knapsack problem maximizes the value subjected to a weight constraint, you can apply it giving as maximum weight $y$, and taking for each $x_i$, $v_i = x_i$ as value and $w_i = x_i$ as it's weight.
I'm pretty sure there's a simpler algorithm, but I can't remember it.
There is in fact a dynamic programming algorithm to solve the unbounded Knapsack Problem. In Rosettacode you can find the algorithm implemented in a great variety of languages.
A: This is a special case of the Knapsack Problem.  It is NP-complete, so you won't find a polynomial-time algorithm.  The dynamical programming algorithm is pseudo-polynomial-time: polynomial in $n$ and $y$, but not in the size of the input (which would be $n \log(y)$).  There are also good heuristic methods that may have a high probability of obtaining a solution when there is one.
A: This problem can be solved using concepts of dijkstra algorithm and number theory.
If we know smallest reachable number $X$ such that $X$ $mod$ x$_i$ = $rem$, then you can reach all larger numbers with such remainder $modulo$ x$_i$ as well, by simply adding x$_i$ one or more times.
The complete description of the algorithm can be found here.
