c# - 如何检查一个整数是否是给定整数的总和？

Question

假设我有一个整数 result 和一个整数数组，假设 [a,b,c](不是固定长度)。我需要检测 result=a*i +b*j + c*k 是否为 i,j,k>=0。

如果可能的话，我更喜欢 C/C# 中的解决方案。

PS 问题来自预订系统，如果行程的持续时间是给定持续时间的组合，则可以出售行程。

谢谢!

例如:如果我们有 a=3, b=7 比结果 20 = 3*2 + 7*2 结果 9 = 3*3 + 7*0

Answer 1

这是 Frobenius Problem这通常是 NP-Hard。

不过，对于小实例，相当快的算法是已知的。

这里的论文:http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf似乎描述了以前的算法(其中包括 Dijkstra 最短路径算法的应用!)加上它提供了一种明显比以前的算法更快的新算法。

在任何情况下，对于只有 2 个数字 a 和 b 使得 gcd(a,b) = 1 的情况，找到 i, j >= 0 使得 ai + bj = M 很容易解决。

众所周知，任何大于 (a-1)(b-1) 的数都可以以 ai + bj 的形式表示，其中 i >=0 and 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 足够小，您也许可以暴力破解它。