檢查線性和爲零的算法

給出一個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

檢查線性和爲零的算法

回答

相關問題