將一個數組劃分爲兩個相等大小的子集，它們的總和差值最小

給定一組n個整數，將該集合劃分爲n/2個大小的兩個子集，使得兩個子集之和的差爲儘可能最小化。如果n是偶數，那麼兩個子集的大小必須嚴格爲n/2，如果n是奇數，那麼一個子集的大小必須是（n-1）/ 2，其他子集的大小必須是（n + 1）/ 2 。例如，給定集合{3,4,5，-3,100,1,89,54,23,20}，集合的大小爲10.該集合的輸出應該是{4，5，-3， 100,1,23,20}和{3,5，-3,89,54}。兩個輸出子集的大小均爲5，兩個子集中的元素總和相同（148和148）。另一個例子，其中n是奇數。設給定集合爲{23,45，-34,12,0,98，-99,4,189，-1,4}。輸出子集應該是{45，-34，12，98，-1}和{23,0，-99，4，189，4}。兩個子集的元素總數分別爲120和121。將一個數組劃分爲兩個相等大小的子集，它們的總和差值最小

經過多次搜索，我發現這個問題是NP-Hard。因此，多項式時間解決方案是不可能的。不過，我正在想這樣的行：

初始化第一個子集作爲第一個元素。
將第二個子集初始化爲第二個元素。
然後根據哪個子集的大小較小以及哪個子集的總和不足，我將插入下一個元素。

以上可能會達到線性時間，我猜。

但是，這裏給出的解決方案太複雜了：http://www.geeksforgeeks.org/tug-of-war/。我無法理解它。因此，我只想問，我的解決方案是否正確？考慮到這是一個NP難題，我認爲它應該這樣做？如果沒有，請問有人可以簡單地解釋一下，鏈接上的代碼究竟是如何工作的？謝謝！

來源

2015-07-03 John Lui

您的解決方案是錯誤的。

這是一個貪婪的方法來解決Subset-Sum問題/分區問題，失敗。

下面是一個簡單的計數器例如：

arr = [1,2,3]

你的溶液將分配A = {1}，B = {2}，然後選擇分配3至A，並獲得A={1,3}, B={2} - 這是不最佳的，因爲最佳的解決方案是A={1,2}, b={3}

它使用動態規劃，通過以下的遞推公式做正確的做法：

D(x,i) = false i < 0 
D(0,i) = true 
D(x,i) = D(x,i-1) OR D(x-arr[i],i-1)

可以通過建立一個遵循自下而上的循環表的動態規劃來高效地完成它。

該表將是大小(SUM/2 + 1)*(n+1)（其中SUM是所有元素的總和），然後在表中查找，使得D(x,n) = true

來源

2015-07-03 20:20:49 amit

你的例子是正確的最大值。得到它了。但是，儘管您的方法聽起來正確，但我仍然無法正確理解它。你能否多加一些關於'D（x，i）'的描述以及真假是什麼意思？ –

@JohnLui'D（x，i）'表示您可以使用第一個'i'元素的元素得到sum'x'的一個子集。這意味着'D（SUM/2，n）'意味着使用列表中的任何元素都有一個大小爲「SUM/2」的子集。 – amit

將一個數組劃分爲兩個相等大小的子集，它們的總和差值最小

回答

相關問題