Minimal non-negative linear combination of positive integers larger than a positive integer

Question

The problem is the following:

We have a positive integer $w$. A set of positive integers $A$ such that $\forall a \in A$ it's true that $a \leq w$. We search for the minimal integer $x$ such that $w \leq x$ and there is a convex integer combination of the elements of $A$ that is equal to $x$. The problem can clearly be written as an integer program but that's not much help.

My best approach is $O(w)$ in both time and space similar to knapsack's dynamic programming solution.

Could someone suggest a better one?

---

EDIT: I made 2 mistakes in the formulation. The first is that the combination is not convex only non-negative. The second is the algorithm I mentioned is not $O(w)$ but $O(|A|w)$.

The algorithm is like make an array size of $w$, sign $0$ in it and unsign everything else. Set a variable $\min$ to "infinite". Go through the array and to each signed element add each element of $A$. If it's not smaller than $w$ but smaller than $\min$ it's the new $\min$. If it's smaller than $w$ sign the according element. When we reach the end of the array $\min$ holds the $x$ in question.

Also the problem can be reformulated as a series of $n$ variable diophantine equation so if $A = \{a_{1}, \ldots, a_{n}\}$ and $d = \gcd(a_{1}, \ldots, a_{n})$ then we only need to check for $x \in \mathbb{N}, w \leq x, d \mid x$ if the diophantine equation $\sum_{i = 1}^{n}y_{i} a_{i} = x$ has an all non-negative $Y = \{y_{1}, \ldots, y_{n}\}$ solution.

I don't know the complexity for this second approach. I don't know how long the series can be.

EDIT.2: The length of the series is the smaller problem. Solving any of the above diophantine equations is like solving the subset-sum problem so this approach is not good either.

Answer 1

This is a variant of making change with a given set of coins, for which the knapsack/dynamic programming algorithm seems to be the best that is known. E.g., http://www.algorithmist.com/index.php/Coin_Change

Answer 2

This is not an answer, but more like a comment. But this is too long to be a comment.

There is a related problem: the computation of the Frobenius number in polynomial time, which is known to be NP-hard (Ramirez-Alfonsin, 1996).

The Frobenius number is defined as follows. Let $a_1,\ldots,a_n$ be positive integers such that $\text{gcd}(a_1,\ldots,a_n)=1$. Then, it's known that there exists a (unique) number $b$ that cannot be represented as any non-negative integer combination of $a_1,\ldots,a_n$, but every integer larger than $b$ can be represented in such a way. This $b$ is called the Frobenius number of $a_1,\ldots,a_n$.

I would expect, if your problem could be solved in polynomial time then we could compute the Frobenius number in polynomial time too. But I have no clue why this should be true for the moment.