这就是问题：
您有两个长度相等的数组 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] 处的值 > [ti] 处的值，从 t = 5 开始，并且 i = 1，并将 i 的值增加 1 并将 t 的值减少 1。
一旦找到匹配项，它就会交换两个索引的值并对从 [t-1] 开始的值进行排序。结果值列表是输出。
我不知道这个算法有什么问题，但它对所有测试用例产生了错误的答案。我知道它可以使用动态编程来解决，并且它是分区问题的一种变体。但我不知道如何改变分区算法来解决这个问题。
将问题简化为分区问题：D[i] = B[i] - A[i]为每个i.
现在问题是数组 上的一个经典分区问题D，您可以使用它的 DP 解来获得伪多项式时间解。
正确性证明：
如果D( sum(D_1) = sum(D_2)) 上有一个解决方案 - 则i_1,...,i_k选择 toD_1并j_1,...,j_m选择 to 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。
另一个方向是相似的。
量子点
问题的复杂性：
问题仍然是 NP-Hard 的简单归约：
给定分区问题 ( S=[a_1,a_2,...,a_n]) 的实例，创建此问题的实例：
A=S, B=[0,...,0]
很容易看出，对这个问题给出最优解的同一解将是对原始分区问题所需的分区，因此该问题是 NP-Hard。