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

Question

可以说我有一个整数result和一个整数数组，可以说[a,b,c]（不是固定长度）。我需要检测 if result=a*i +b*j + c*k， with i,j,k>=0。

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

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

谢谢！

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

Answer 1

这是Frobenius 问题，通常是 NP-Hard。

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

这里的论文：http: //www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf似乎描述了以前的算法（其中包括 Dijkstra 最短路径算法的应用！）加上它提供了一种新算法，显然比以前的。

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

还已知任何大于 (a-1)(b-1) 的数都可以表示为 a i + b j 的形式，其中 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 足够小，您可能只能强行将其淘汰。

Answer 2

您的问题陈述太模糊而无法确定 - 如果输入向量不是固定长度，i、j、k 的可能值是多少？

在我看来，您的问题似乎是背包问题的变体。