<p>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., <a href="http://www.algorithmist.com/index.php/Coin_Change" rel="nofollow">http://www.algorithmist.com/index.php/Coin_Change</a></p>

CC BY-SA 2.5
2011-03-31T12:44:29.507Z
How do you find the smallest x? In the coin change problem x is given.
Marcus Ritt
CC BY-SA 2.5
2011-03-31T13:24:22.250Z
The dynamic programming solution finds all amounts that can be made up to, say, w+max(A).
Jack
CC BY-SA 2.5
2011-03-31T11:48:40.833Z
2011-03-31T11:48:40.833Z
Jack
<p>This is not an answer, but more like a comment.  But this is too long to be a comment.</p>

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

<p>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 <em>Frobenius number</em> of $a_1,\ldots,a_n$.</p>

<p>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.</p>

CC BY-SA 2.5
2011-03-31T14:09:26.453Z
2011-04-01T00:02:16.457Z
2011-04-01T00:02:16.457Z
Yoshio Okamoto
<p>The problem is the following:</p>

<p>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.</p>

<p>My best approach is $O(w)$ in both time and space similar to <a href="http://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem" rel="nofollow">knapsack's dynamic programming solution</a>.</p>

<p>Could someone suggest a better one?</p>

<hr>

<p>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)$. </p>

<p>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.</p>

<p>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.</p>

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

<p>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.</p>

CC BY-SA 2.5
2011-03-30T23:06:39.900Z
what's a convex integer combination ? convexity is usually defined as  positive numbers summing to 1.
Suresh Venkat
CC BY-SA 2.5
2011-03-30T23:37:30.177Z
It's hard to believe the problem can be solved in O(w), which is independent of the size of A.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-31T21:41:04.690Z
I think it will be nice if you provide some background about why you are interested in this problem.
Kaveh
CC BY-SA 3.0
2012-12-02T05:03:42.457Z
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
<ds.algorithms><integer-programming>
Minimal non-negative linear combination of positive integers larger than a positive integer
jakab922
# Minimal non-negative linear combination of positive integers larger than a positive integer

(Asked by: username_0 on 2011-03-30)

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](http://en.wikipedia.org/wiki/Knapsack_problem#Unbounded_knapsack_problem).

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.

**Tags:** ds.algorithms, integer-programming

> **Comments:**
> **username_1**: what's a convex integer combination ? convexity is usually defined as  positive numbers summing to 1.  
> **username_2**: It's hard to believe the problem can be solved in O(w), which is independent of the size of A.  
> **username_3**: I think it will be nice if you provide some background about why you are interested in this problem.  
> **username_4**: 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.  

---

## 2 answers

### Answer by username_5 on 2011-03-31. Score: 3

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>

> **Comments:**
> **username_6**: How do you find the smallest x? In the coin change problem x is given.  
> **username_5**: The dynamic programming solution finds all amounts that can be made up to, say, w+max(A).  

---

### Answer by username_2 on 2011-03-31. Score: 1

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.


---

