Given $n$ integers $a_1$ to $a_n$ and an integer $K$, does there exist a solution which satisfies the following equation?

Question

Given $n$ integers $a_1$ to $a_n$ and an integer $K$, does there exist a solution which satisfies the following equation?

$$\sum_{i=1}^n a_i\cdot x_i = K $$

Note that all $x_i$ must need to be NON-NEGATIVE integers.

My Attempt: This seems to be a NP-hard problem, special kind of Knapsack problem with exact value to match. I don't have much idea apart from brute force on entire range like a knapsack problem. Someone told me it can be solved efficiently by graph theory .

Answer 1

The coin problem, also called Frobenius problem, is probably what you are looking for: https://en.wikipedia.org/wiki/Coin_problem

It is the problem of finding the largest $K$ that is not reachable, given the $a_i$.

For the problem to have a solution, the $a_i$ must have no common divisor greater than 1.

As for finding a solution with a computer:

• As we know that for 2 $a_i$ $x$ and $y$ (EDIT: which are coprime), the largest non-reachable number is $xy - x - y$, if $K$ is greater than this (for the two smallest coprime $a_i$) then the problem is solved positively.

• If not, then a brute force approach may not be too much costly, because the $a_i$ will be roughly greater than $\sqrt K$.