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

Question

我有一道关于数组算法设计的题，应该用C语言实现。假设我们有一个包含 n 个元素的数组。为简单起见，n 是“2”的幂，例如 1、2、4、8、16 等。我想用 (n/2) 元素将它分成两部分。分离的条件是两个数组中所有元素之和的最小绝对差值 例如，如果我有这个数组(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

这是 Partition Problem ，不幸的是 NP-Hard .

但是，由于您的数字是整数，如果它们相对较低，则存在使用 Dynamic Programming 的伪多项式 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

稍后，您可以通过返回表格并“回溯”您在每一步的选择来获得相关的子集。 This thread处理如何处理一个非常相似的问题。

---

对于小集合，还有一个简单的暴力解决方案的替代方案，它基本上将数组分成所有可能的两半((2n)!/(n!*n!) )，然后从中选出最好的一个。