数，使一个序列的总和

Question

在观看橄榄球昨晚我在想，如果任何给定的分数，你只能得分在很多3,5或7。它没有多久就制定出任何数量大于4是可以实现的是不可能的。 5 = 5,6 = 3 + 3,7 = 7,8 = 3 + 5,9 = 3 + 3 + 3，10 = 5 + 5等等。

上延伸这一想法为5,7和9倍的产率如下可能的分数：

5,7,9,10,12,14 // and now all numbers are possible.  

有关7,9和11：

7,9,11,14,16,18,20,22,23,25,27 // all possible from here

我没有这在我的头上，任何人都可以提出一个很好的算法，将确定最低可能得分高于其所有得分是可以实现给定一组分数。

我仿照它是这样的：

forall a < 10:
   forall b < 10:
      forall c < 10:
          list.add(3a + 5b + 7c);
list.sort_smallest_first();

然后检查一序列比3长列表（最小得分可能）。似乎很不切实际，慢超越平凡情况下任何东西。

Answer 1

有只有一个无法实现的数目高于该所有得分是可以实现的。

这就是所谓的弗罗贝纽斯号码。参考： http://en.wikipedia.org/wiki/Frobenius_number

在wiki页面应该有链接，算法来解决它，例如： HTTP： //www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

有关2号A，B的精确配方（AB-AB）是已知的（它可以使用，以减少搜索空间），以及用于3个数字的a，b，CA尖锐下界（SQRT（3ABC） - ABC）和相当快的算法是已知的。

如果数字是算术级数，然后一个确切的配方是已知的（见维基）。我提到这一点，因为在你的例子所有数字算术级数。

因此，要回答你的问题，找到弗罗比尼斯范数量和其加1。

希望有所帮助。