检查线性和为零的算法

给出一个N非负整数的列表，提出一个算法来检查列表中的X数字的总和是否等于剩余的N-X。检查线性和为零的算法

换句话说，一个简单的案例Subset sum problem它涉及整个集合。

的尝试的解决方案

排序列表的降序排列的元素。初始化变量SUM到第一个元素。删除第一个元素（最大，a(1)）。假设a(n)表示当前列表中的n-th元素。

尽管列表中有一个以上的元素，

让SUM等于SUM + a(1)或SUM - a(1)，取最接近a(2)。（最近意味着|a(2) - SUM_POSSIBLE|最小）。
删除a(1)。

如果SUM等于-a(1)或a(1)，存在线性总和。

问题

我似乎无法来解决上面的算法，如果是正确的，我想证明。如果它是错误的（更可能），是否有办法在线性时间完成这项工作？

PS：如果我做错了，请原谅：您要小号

来源

2012-07-29 Furlox

通知x数之和等于其他N-x数的总和。
你可以简化这个，说你想看看是否有一个子集总和为S/2其中S是整个集合的总和。所以，你可以计算一次迭代所需的总和（O（n））。

然后，只需使用已知的算法，如Knapsack找到符合您的总和的子集。

另一个更 “数学” 的解释：Dynamic Programming – 3 : Subset Sum

编辑：

作为回答您的其他问题，你的算法是错误的。考虑号码的这个名单：

{3,3,4,4}

总和为14，那么你正在寻找与7总和的一个子集很显然，这将是3 + 4 。

你的算法在检查2 3之后会返回假

来源

2012-07-29 06:40:53

我想你错过了排序部分。 '{3,3,4,4}' - >'{4,4,3,3}'，它会在'4 + 4 = 7'上正确地选择'4-4 = 0'为| 0-3 | = 3 <| 7-3 | = 4'。现在可以在列表的其余部分调用所提出的算法。你的答案的其他部分我明白，但我认为我提出的算法会更快（如果证明是正确的）。感谢闪电般的快速反应！ – Furlox 2012-07-29 07:09:48

我刚刚看到[分区问题]（http://en.wikipedia.org/wiki/Partition_problem），这正是我们一旦发现“S”是偶数就想要做的事情。作为奖励，我的算法也打破了贪婪的反例。最后感谢Yochai：D – Furlox 2012-07-29 07:44:38

检查线性和为零的算法

回答

相关问题