用於將整數轉換爲具有零和的桶的算法

Question

假設我們有一個整數數組（負數和正數）A[1 ... n]，使得所有元素總和爲零。現在，每當我有一堆總和爲零的整數時，我會稱它們爲組，並且我想盡可能多地將拆分爲不相交組。你能建議任何論文討論這個同樣的問題嗎？

Answer 1

聽起來像你的問題包含兩個NP完成問題。

第一個將找到解決子集總和問題的所有子集。這個問題確實具有指數時間複雜性（正如評論中的amit所暗示的那樣），但從理論角度來看，它是子集和問題的一個非常合理的擴展。例如，如果您可以通過動態編程解決子集總和問題並生成規範的二維數組，那麼該數組將包含足夠的信息以使用回溯生成所有可能的解決方案。

嵌入問題中的第二個NP-Complete問題是整數線性規劃問題。給定解決子集總和問題的所有可能的子集，N total，我們想要選擇0 < = n < = N，使得n的值最大化並且A的元素不重複。

我懷疑是否有專門用於描述這個問題的出版物，因爲它似乎涉及已知理論的直接應用。