两个列表元素总和比较的最小复杂度

Question

关于数组的算法设计我有一个问题,应该用C语言实现.假设我们有一个有n个元素的数组.为简单起见,n是'2'的幂1, 2, 4, 8, 16 , etc.我想用(n/2)元素将它分成两部分.分离的条件是lowest absolute difference between sum of all elements in two arrays,例如,如果我有这样的阵列(9,2,5,3,6,1,4,7)将是单独的对这些阵列(9,5,1,3)和(6,7,4,2).第一个数组的元素18的总和是和第二个数组的元素的总和是19,差异是1,这两个数组是答案,但是两个数组喜欢(9,5,4,2)并且(7,6,3,1)不是答案,因为元素求和的差异是4我们已经找到的1.所以4不是最小的差异.怎么解决这个？谢谢.

Answer 1

这是分区问题,遗憾的是NP-Hard.

但是,由于您的数字是整数,如果它们相对较低,则O(W*n^2) 使用动态编程存在伪多项式解决方案(其中W所有元素的总和).

我们的想法是(W/2+1)*(n+1)*(n/2+1)根据以下递归公式创建大小的DP矩阵:

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

上面给出了一个3d矩阵,其中每个条目D(x,i,k)表示是否有一个包含确切k元素的子集,它们总和x,并使用第一个i元素作为候选.

一旦你有了这个矩阵,你只需要找到最高的x(小于SUM/2)D(x,n,n/2) = true

之后,您可以通过返回桌面并在每一步"回溯"您的选择来获得相关的子集.这个主题讨论如何在一个非常类似的问题上完成它.

对于小型集合,还有一种天真的暴力解决方案的替代方案,它基本上将阵列分成所有可能的一半((2n)!/(n!*n!)那些),并从中挑选出最好的一半.