How to check if an integer is the sum of given integers?

Question

Suppose I have an integer result and an array of integers, say [a,b,c] (not a fixed length). I need to determine if result=a*i +b*j + c*k , with i,j,k>=0 .

I prefer a solution in C / C # if possible.

PS The problem is the reservation system, a trip can be sold if its duration is a combination of a given duration.

Thank!

Ex: if we have a = 3, b = 7 than result 20 = 3 * 2 + 7 * 2 result 9 = 3 * 3 + 7 * 0

Answer 1

This is a Frobenius problem , which is generally NP-Hard.

For small instances, fairly fast algorithms are known.

The article here: http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf seems to describe previous algorithms (including the Dijkstra shortest path algorithm application!) Plus this gives a new algorithm, which seems to be faster previous ones.

In any case, for the case when there are only 2 numbers, a and b such that gcd (a, b) = 1, finding i, j> 0, that ai + bj = M is easily solved.

It is also known that any number greater than (a-1) (b-1) can be represented as ai + bj with i> = 0 and j> = 0. The Frobenius number is defined as the largest number that cannot be represented in this form, it exists when n> = 2 and gcd (a, b, c ...) = 1.

So, in your case, if the numbers involved are small enough, you can sort the array, find the "smallest" two a and b, such as gcd (a, b) = 1 and see if M> (a-1) ( b-1), which can only be solved with a and b.

if M <= (a-1) (b-1) and a and b are small enough, you can simply force the exile.

Answer 2

Your statement of the problem is too vague to be sure - what are the possible values ​​of i, j, k ... if the input vector is not a fixed length?

It seems to me that your problem is a variation of the backpack problem .