哪種算法可以用來解決分區概率的這種變化？

Question

這就是問題所在：

你有兩個長度相等的數組A和B.你必須將它們分成兩組P和Q，使得： （1）它們的差別被最小化。 （2）如果A [i]進入P或Q之一，B [i]應該進入另一個。

下面是實際的問題的鏈接：http://opc.iarcs.org.in/index.php/problems/EQGIFTS

這是我的邏輯（解決實際問題）：

如果輸入是：ABCDEFG，值的列表和 索引a，b，c，d，e，f分別爲0,1,2,3,4,5

如果t是a，b，c，d，e，f，g的索引，程序會檢查對於t和i這樣的：在[t]處的值[t]處的值，從t = 5開始，並且i = 1，並且將i的值增加1並且減小噸 的由1

只要它找到一個匹配值時，它交換兩個索引的值 和排序的值從開始[T-1]。 產生的值列表是輸出。

我不知道這個算法有什麼問題，但是它對所有的測試用例都會產生錯誤的答案。 我知道它可以使用動態編程來解決，而且它是分區問題的變體。但是我不知道如何改變分區算法來解決這個問題。

Answer 1

問題縮小到分區的問題：
每個i創建一個第三陣列D[i] = B[i] - A[i]。

現在問題是陣列D上的經典partition problem，您可以使用其DP解決方案來獲得僞多項式時間解。

正確性證明：
如果有上D（sum(D_1) = sum(D_2)）中的溶液 - 再就是i_1,...,i_k選擇D_1和j_1,...,j_m選擇D_2（以及每個索引是在我的或j的），使得：

sum(D[i's]) = sum(D[j's]) 

從建築，它的意思是：

sum(B[i]-A[i]) = sum(B[j]-A[j]) (for each relevant i's,j's) 

因而：

sum(B[i's]) - sum(A[i's]) = sum (B[j's]) - sum(A[j's]) 

從這：

這正是我們想要的，因爲每一個「指標」分配給兩個部分

sum(B[i's]) + sum(A[j's]) = sum(B[j's]) + sum(A[i's]) 

，一部分得到了B和其他得到A.
另一個方向是相似的。

QED

---

複雜性的問題：
問題依舊NP-硬用簡單的還原：

鑑於劃分問題（S=[a_1,a_2,...,a_n]）的一個實例，創建實例問題：

A=S, B=[0,...,0] 

很容易看到解決此問題的最佳解決方案的相同解決方案將成爲對原始分區問題的所需分區，因此問題是NP-Hard。