算法整数

的总和

可能重复：
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 - 第一个最小的更大的一个。

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

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

感谢，西蒙

来源

2012-05-16 simonxy

你认为@Simonxy的做法是什么？你有什么想法吗？ – Yavar

作业？如果是，请添加一个标签'homework' – Crazenezz

在sum = 12的例子中，有几个解决方案（2,4,6,8,4）。应该找到他们？否则，这两种解决方案是等价的还是一种比另一种更好？ –

这就是所谓subset sum问题的一般化情况。这是一个NP完全问题，因此最着名的算法是pseudo-polynomial。如果您了解上述链接算法，则可以扣除解决问题所需的修改。

来源

2012-05-16 07:53:35 kosii

你有一些例子吗？谢谢。 – simonxy

如何递归呢？

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-16 08:09:51 Guffa

通过这种方式可以杀死内存：'int [] rest = ...，with = ...，without = ...'和递归调用。 –

@SaeedAmiri：行为在记忆之前成为问题looooong。对于有20个值的数组，最大内存使用量约为2 kb。 – Guffa

我花了大约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-16 08:21:41

注意*：只是为了让你采取多种方式之一来做到这一点，当然有更好的方式来解决这个问题，你仍然必须添加错误处理和类似的东西，但我有点喜欢测试它在最后你可以使用像这样的东西：http://jesuso.net/projects/selectExactSum/index.php?numbers=5%2C2%2C8%2C4%2C6&reqSum=105它仍然有效：D 所以，你只要你有1对和1个奇数，或者给定的数字只有1，就可以和任何数字相加。 –

您可以在ideone.com上发布您的代码 –

当我阅读您的代码（我不是php）时，我不确定它是否正常工作。你能用JavaScript或C＃解释吗？ – simonxy

回答

相关问题