c# - 整数和的算法

<分区>

Possible Duplicate:
Finding all possible combinations of numbers to reach a given sum

我必须创建从数字数组中选择数字的方法，该方法的总和将与要求的数字完全一致，或者如果不存在则选择最小的更大的数字。这个函数的算法是什么？

public int[] selectExactSum(int[] X, int SUM) {
}

例子: 数字是:{5, 2, 8, 4, 6}，要求的总和是 12。

结果将是:{2, 4, 6}

如果要求的总和是 13，结果将是:{2, 8, 4} - 因此，在这种情况下，总和将是 14 - 第一个最小的大数。

如果 Required sum 为 15，则可能的结果为:{5, 2, 8} 或 {5, 4, 6}。在这种情况下，返回您选择的一个 - 可能是您得到的第一个。

自定义数字和总和的算法是什么？

谢谢，西蒙

最佳答案

这是一个名为 subset sum 的问题的一般情况.这是一个 NP 完全问题，因此最著名的算法是 pseudo-polynomial . 如果您了解上述链接算法，则可以推导出解决您的问题所需的修改。

关于c# - 整数和的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10613918/

相关文章：

ruby - 算法中的无限循环以匹配以不同速度运行的时钟