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

Question

假设我有一个整数 result 和一个整数数组，比如说 [a,b,c]（长度不固定）。我需要检测是否存在 i,j,k>=0，满足result=a*i +b*j + c*k。

如果可能的话，我更喜欢使用 C/C# 解决这个问题。

PS：这个问题来自一个预订系统，只有当旅游行程的持续时间是给定持续时间的组合时，该行程才能被出售。

例如：如果我们有 a=3，b=7，则结果 20 = 3*2 + 7*2，结果 9 = 3*3 + 7*0。

- user350887

---

一个好问题，但需要澄清首选结果是什么。假设a、b、c是持续时间，而i、j、k是每个持续时间的数量，您更喜欢最少的持续时间数量（i+j+k最小）还是较少的较长持续时间数量（优先考虑较低的a、b、c值）？ - Grace Note

（复杂但相当优化的）https://dev59.com/FUnSa4cB1Zd3GeqPOX2S - sdcvvc

我只想知道是否存在一种组合！ - user350887

你的持续时间是固定的吗？一些参数组合可以通过“贪婪”算法轻松解决，而其中一些 - 幂 - 甚至更简单。 - Nick Johnson

Answer 1

这是 Frobenius问题，一般来说是NP困难的。

虽然已知针对小规模实例有相对较快的算法。

这篇论文：http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf 似乎描述了之前的算法（其中包括Dijkstra的最短路径算法的应用！），并提供了一种新算法，比之前的算法更快。

无论如何，对于仅有两个数字a和b，满足gcd(a，b) = 1，找到i，j ≥ 0使得ai + bj = M很容易解决。

也有人知道，任何大于（a-1）（b-1）的数字 都可以用a + b的形式表示，其中i≥0且j≥0。 当n≥2且gcd（a，b，c ...）= 1时，Frobenius号被定义为无法用该形式表示的最大数字。

因此，在您的情况下，如果涉及的数字足够小，则可以对数组进行排序，找到“最小”的两个a和b，使得gcd（a，b）= 1，并查看是否M>(a-1) （b-1），这可以仅使用a和b解决。

如果M≤（a-1）（b-1），并且a和b足够小，则您可能只能暴力解决。

- Aryabhatta

Answer 2

您的问题陈述过于模糊，无法确定i、j、k等变量的可能取值...如果输入向量长度不固定的话，这些变量应该是什么？

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

- Joris Timmermans