-1

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

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

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}。在这种情况下，返回您选择的一个 - 可能是您得到的第一个。

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

谢谢，西蒙

4

3 回答 3

6

这是称为子集和的问题的一般化案例。这是一个 NP 完全问题，因此最著名的算法是pseudo-polynomial。如果您了解上述链接算法，则可以扣除解决问题所需的修改。

于 2012-05-16T07:53:35.873 回答
1

递归怎么样？

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。

于 2012-05-16T08:09:51.153 回答
0

我花了大约 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#，请告诉我。

于 2012-05-16T08:21:41.960 回答