How to check if a integer is sum of given integers?

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

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

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

Tha开发者_StackOverflow社区nks!

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

This is the Frobenius Problem which is in general NP-Hard.

For small instances, reasonably fast algorithms are known, though.

The paper here: http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf seems to describe previous algorithms (which includes an application of Dijkstra's shortest path algorithm!) plus it gives a new algorithm which is apparently faster than the 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 such that ai + bj = M is easy to solve.

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

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

if M <= (a-1)(b-1), and a and b are small enough, you might just be able to brute force it out.

Your problem statement 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 sounds to me as if your issue is a variation on the knapsack problem.