整数总和的算法

本文关键字：算法 和的 整数 | 更新日期: 2023-09-27 18:34:31

可能的重复项：
找到所有可能的数字组合以达到给定的总和

我必须创建从数字数组中选择数字的方法，其总和将根据需要精确，或者如果不存在，请选择最小的较大数字。这个函数的算法是什么？

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

例：数字为：{5， 2， 8， 4， 6}，所需总和为 12。

结果将是：{2， 4， 6}

如果所需的总和为 13，则结果将是：{2， 8， 4} - 因此，在本例中，总和为 14 - 第一个最小较大的一个。

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

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

谢谢西蒙

整数总和的算法

这是称为子集和的问题的广义情况。这是一个NP完全问题，因此最著名的算法是伪多项式。如果你了解了上面的链接算法，你可以扣除解决你的问题所需的修改。

递归怎么样？

public static int[] SelectExactSum(int[] x, int sum) {
  int[]
    rest = x.Skip(1).ToArray(),
    with = x.Length == 1 ? x : x.Take(1).Concat(SelectExactSum(rest, sum - x[0])).ToArray(),
    without = x.Length == 1 ? new int[0] : SelectExactSum(rest, sum);
  int withSum = with.Sum(), withoutSum = without.Sum();
  return
    withSum >= sum ? (withoutSum >= sum ? (withSum < withoutSum ? with : without) : with) :
    withoutSum >= sum ? without : new int[0];
}

注意：调用SelectExactSum(new int[] {5,2,8,4,6}, 13)不会返回问题中所述的{2,8,4}，而是返回{5,8}，因为这实际上等于13。

我花了大约 15 分钟才完成它，您可以在此处看到它运行：

http://jesuso.net/projects/selectExactSum/index.php?numbers=5%2C2%2C8%2C4%2C6&reqSum=15

这是代码：

http://jesuso.net/projects/selectExactSum/selectExactSum.txt

我使它尽可能简单，但它是在 PHP 上制作的，如果您需要一些帮助将其转换为 c#，请告诉我。

相关文章：