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

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.

• what's a convex integer combination ? convexity is usually defined as positive numbers summing to 1. Mar 30 '11 at 23:06
• It's hard to believe the problem can be solved in O(w), which is independent of the size of A. Mar 30 '11 at 23:37
• I think it will be nice if you provide some background about why you are interested in this problem. Mar 31 '11 at 21:41
• I'm pretty sure that this is weakly NP-hard, and if you want to prove it I would look up information on "unbounded knapsack" and/or "knapsack cover." There is a book by Kellerer, Pferschy and Pisinger which goes into a nice amount of detail on such reductions, which should be enough to prove the hardness. Dec 2 '12 at 5:03

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

• How do you find the smallest x? In the coin change problem x is given. Mar 31 '11 at 12:44
• The dynamic programming solution finds all amounts that can be made up to, say, w+max(A).
– Jack
Mar 31 '11 at 13:24

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.