可以說我有一個整數result和一個整數數組，可以說[a,b,c]（不是固定長度）。我需要檢測是否result=a*i +b*j + c*k，與i,j,k>=0。如何檢查一個整數是給定整數的總和？
如果可能，我更喜歡C/C＃中的解決方案。
PS問題來自預訂系統，如果旅程的持續時間是給定持續時間的組合，則可以出售旅程。
謝謝！
例如：如果我們有A = 3，B = 7 比rezult 20 = 3 * 2 + 7 * 2 結果9 = 3×3 + 7 * 0
你的問題陳述太模糊到可以肯定 - 如果輸入向量不是固定長度，那麼i，j，k的可能值是多少？
這聽起來我好像你的問題是關於knapsack problem.
的變化這是Frobenius Problem這是一般NP難。
雖然對於小型實例，已知合理快速的算法。
這裏的文章：http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf似乎描述了以前的算法（其中包括Dijkstra的最短路徑算法的應用！）加上它給出了一個新的算法，它明顯比以前的算法快。在任何情況下，對於只有2個數字的情況，a和b使得gcd（a，b）= 1，發現i，j> = 0，使得a = 10 i + b j = M很容易解決。
還已知的是任何數量的比（A-1）（B-1）可以可以以的形式表示一個我+ BĴ，大於其中i> = 0且j> = 0。 Frobenius數被定義爲不能以這種形式表示的最大數字，並且當n> = 2且gcd（a，b，c ...）= 1時存在。
所以在你的情況下，如果所涉及的數字是足夠小的，你可以排序數組，找到'最小'兩個a和b，使得gcd（a，b）= 1，並且看看M>（a-1）（b-1），哪個可以只需使用a和b即可解決。
如果M < =（a-1）（b-1），並且a和b足夠小，那麼您可能就可以將其強制推出。
一個很好的問題，但是對於最佳結果是什麼進行了澄清。假設a，b，c是持續時間，而i，j，k是每個持續時間的數量，那麼你更喜歡最少的持續時間計數（i + j + k是最小的）還是更長的持續時間數量越少a，b，c）的值？ – 2010-05-26 12:32:47
http://stackoverflow.com/questions/1467907/（複雜但相當優化） – sdcvvc 2010-05-26 12:35:19
我只想知道一個組合是否存在！ – user350887 2010-05-26 12:43:17