2

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

换句话说，涉及整个集合的子集和问题的更简单情况。

尝试的解决方案

按降序对列表的元素进行排序。将变量初始化SUM为第一个元素。删除第一个元素（最大，a(1)）。让a(n)表示n-th当前列表中的元素。

虽然 list 有多个元素，

  1. 使SUM等于SUM + a(1)或SUM - a(1)，以最接近的为准a(2)。（其中最接近的均值|a(2) - SUM_POSSIBLE|是最小值）。

  2. 删除a(1).

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

问题

我似乎无法解决上述算法，如果它是正确的，我想要一个证明。如果它是错误的（更有可能），有没有办法在线性时间内完成？

PS：如果我做错了什么，请原谅：S

4

1 回答 1

1

请注意，您希望数字的总和x等于其他N-x数字的总和。
您可以通过说您想查看是否存在一个子集来简化这一点，该子集的总和S/2是S整个集合的总和。

因此，您可以通过一次迭代 ( O(n) ) 计算出所需的总和。

然后只需使用像背包这样的已知算法来找到满足您总和的子集。

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

编辑：

作为对您其他问题的回答，您的算法是错误的。考虑这个数字列表：

{3,3,4,4}

总和为 14，因此您正在寻找总和为 7 的子集。显然它将是 3+4。

检查 2 个 3 后，您的算法将返回 false

于 2012-07-29T06:40:53.040 回答