algorithm - 哪种算法可用于解决分区概率的这种变化？

Question

问题是:

您有两个长度相等的数组 A 和 B。您必须将它们分成两组 P 和 Q，这样:(1) 将它们的差异最小化。(2) 如果 A[i] 进入 P 或 Q 之一，B[i] 应该进入另一个。

这里是实际问题的链接:http://opc.iarcs.org.in/index.php/problems/EQGIFTS

这是我的逻辑(解决实际问题):

如果输入是:a b c d e f g，值列表和索引a,b,c,d,e,f分别为0,1,2,3,4,5

如果 t 是 a,b,c,d,e,f,g 的索引，程序会检查 t 和 i 这样的即:[t] 处的值 > [t-i] 处的值，从 t = 5 开始，并且 i= 1, 将 i 的值增加 1 并减少 t 的值1.

一旦找到匹配项，它就会交换两个索引的值并对从 [t-1] 开始的值进行排序。结果值列表是输出。

我不知道这个算法有什么问题，但它对所有测试用例都产生了错误的答案。我知道它可以使用动态规划来解决，并且它是分区问题的变体。但是我不知道如何改变分区算法来解决这个问题。

Answer 1

将问题归结为分区问题:
为每个i创建第三个数组D[i] = B[i] - A[i]。

现在这个问题很经典了partition problem在数组 D 上，您可以使用其 DP 解决方案来获得伪多项式时间解决方案。

正确性证明:
如果在D上有解(sum(D_1) = sum(D_2))-那么有i_1,...,i_k 选择到 D_1 和 j_1,...,j_m 选择到 D_2 (每个索引都在 i 或 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-Hard:

给定分区问题实例 (S=[a_1,a_2,...,a_n])，创建此问题的实例:

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

很容易看出，给出该问题最优解的相同解将是原划分问题所需的划分，因此该问题是NP-Hard问题。