组合值的算法
组合值的算法
提问于 2011-03-21 20:12:53
我试着为给定的问题写一个算法：
我们得到了一组数字- {n1，n2，n3，n4，n5……}，我们必须检查我们是否可以用给定的数字进行加法和减法得到一个数字(比如X)。X总是小于给定集合的所有元素。
例如：
集合：{2,3,4,6,9}
给定数量: 1，结果:是
9-4-4 =1
集合：{3,4,6,9}
给定数量: 2，结果:是
6-4 =2
提前谢谢。
回答 2
Stack Overflow用户
回答已采纳
发布于 2011-03-21 20:18:56
实际上，您正在寻找由集合中的数字生成的ideal。整数形成一个principal ideal domain，这意味着每个理想都是由一个整数生成的。你所要做的就是找到这个整数--比如说g --并检查X是否能被g整除。找到g也很容易--它是集合中所有元素的最大公约数，可以用Euclidean algorithm找到。
示例集合可以通过加法和减法生成每个整数，因为可以生成1。例如，对于集合{3,4,6,9}，您有1= 4-3，并且任何整数n都可以写为4-3之和的n倍。
Stack Overflow用户
发布于 2011-03-21 20:20:01
假设在第一个示例中，您可以多次使用一个数字。
给定的数字必须是您设置的GCD的倍数。这是唯一的条件。它有多大并不重要。
如果您只需要一个是/否的答案，那么找到GCD就足够了。如果您还想要一个给定数字的表达式，那么可以用查找GCD的表达式来解决这个问题。
GCD = X+Y+..+Z-T-U-...-V页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/5377413
复制相关文章
相似问题
腾讯云开发者
