3
$\begingroup$

Given a positive integer y and n positive integers x1 , x2 , ... , xn does there exist non negative integers a1 , a2 , ... , an such that:

$$y = a_1 x_1 + a_2 x_2 + \dots + a_n x_n$$

The problem is just to answer if such ai's exist or not.

My approach was to check for a given y if either of (y - xi) for i in [1..n] is expressible as a linear combination of xi's recursively and base case being that all xi's are expressible. But this approach is too slow for large values of y.

Is there some alternate faster approach?

$\endgroup$

migrated from cs.stackexchange.com Jul 21 '16 at 17:57

This question came from our site for students, researchers and practitioners of computer science.

  • $\begingroup$ Welcome to CS.SE! It sounds like you're asking "what is the condition under which $a_i$'s exist?", and that is a pure math problem, so off-topic here -- but potentially on-topic over at Math.SE. I'll migrate your question over there. P.S. It's not clear what $x$ represents in your approach; I don't see an $x$ in the problem statement. Did you mean $y$ instead of $x$? $\endgroup$ – D.W. Jul 21 '16 at 17:56
  • $\begingroup$ Yes, either the conditions for y under which $a_i$'s exist or y's which can be expressed as a linear combination of $x_i$'s with non negative coefficients. I have edited my approach statement to make it clearer $\endgroup$ – eager Jul 21 '16 at 19:04
1
$\begingroup$

This reminds me of the subset sum problem, which happens to be NP-Complete. It's also related to the Knapsack Problem, which, given your problem statement, seems to fit quite nicely.

As the Knapsack problem maximizes the value subjected to a weight constraint, you can apply it giving as maximum weight $y$, and taking for each $x_i$, $v_i = x_i$ as value and $w_i = x_i$ as it's weight.

I'm pretty sure there's a simpler algorithm, but I can't remember it.

There is in fact a dynamic programming algorithm to solve the unbounded Knapsack Problem. In Rosettacode you can find the algorithm implemented in a great variety of languages.

$\endgroup$
  • $\begingroup$ Why would you suggest taking different weights for different values of $x_i$'s. Wouldn't they all have equal weights (say 1) as we have no preferences on choosing either of $x_i$'s. We are not looking for minimizing the coefficients $a_i$'s. $\endgroup$ – eager Jul 23 '16 at 7:14
  • $\begingroup$ @user6370652 because the Knapsack algorithm maximizes the total value while keeping the weight under a constraint. To apply the algorith to the sum, your $y$ is the weight constraint and also the target value you'd like the algorithm to output. By setting each $x_i$'s value and weght to $x_i$, you force the algorithm to give you the maximum sum less than or equal to $y$. If the final total value is less than $y$, then it doesn't exist a linear combination of the $x_i$ (with integral coeffiecients $a_i$) which sums $y$. $\endgroup$ – miravalls Jul 24 '16 at 8:17
1
$\begingroup$

This is a special case of the Knapsack Problem. It is NP-complete, so you won't find a polynomial-time algorithm. The dynamical programming algorithm is pseudo-polynomial-time: polynomial in $n$ and $y$, but not in the size of the input (which would be $n \log(y)$). There are also good heuristic methods that may have a high probability of obtaining a solution when there is one.

$\endgroup$
1
$\begingroup$

This problem can be solved using concepts of dijkstra algorithm and number theory.

If we know smallest reachable number $X$ such that $X$ $mod$ x$_i$ = $rem$, then you can reach all larger numbers with such remainder $modulo$ x$_i$ as well, by simply adding x$_i$ one or more times.

The complete description of the algorithm can be found here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.