# 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. – Suresh Venkat 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. – Yoshio Okamoto 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. – Kaveh 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. – daveagp Dec 2 '12 at 5:03

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$.