1
$\begingroup$

Let's say I have a set of non-negative integers $a_1,..,a_n$ and a number $C$ which is a non-negative constant (an integer).

Consider an equation

$x_1\cdot a_1 + x_2\cdot a_2 + ... + x_n\cdot a_n - C = 0$

where $x_1,...,x_n$ are unknown non-negative integers. I have to say whether a solution to this equation exists, and when does it exist and when does it not exist.

I'd really appreciate anyone's help I've been struggling with this one for quite a while.

EDIT
Well so far i haven't made a good progress, i'm going to sleep and see you all in the morning.So far i got two conclusion. 1.) if the number C is not divisible by the gcd of the set than there certainly is no solution 2.)If C is divisble by gcd, If we divide all the numbers by the gcd than it becomes Frobenius coin problem.I'm now looking into upper bounds for FCP.See you all in the morning.

  • 0
    Will dynamic programming give definitive answers of the type *If the numbers $a_i$ have no common divisors, then all sufficiently large $C$ can be written in this form*?2012-12-07

2 Answers 2

1

This way is really inefficient for a large number of variables, but Integer Programming is a built-in feature in most scientific computation software these days.

Try to find whether this Integer Program has a solution

$\mathbf{min} \sum_ix_i$ $s.t. \sum_i a_i x_i = C$ $x_i \geq0$ where all $x_i$ are integers. This will give you a dirty but easy answer.

Note: The objective function $\sum x_i$ is just a placeholder. It can be replaced by any other increasing function. If the software supports it, even $\mathbf{min}\mbox{ } 0$ is fine. Thanks to Jacob for pointing it out.

  • 0
    yeah. that is fine. I was just trying to formulate it as an IP.2012-12-05
0

Solve it as a knapsack problem. $a_i$ is your weight, $x_i$ is the quantity of each item and set the "value" for each $x_i$ as 1. $C$ is the total weight your knapsack can carry. If you do find a solution, check if the total "weight" is equal to $C$ ; then you have a solution.