将一组值分成两个大小相同或相似且值和相似的集合

Question

我有一组浮点值，我想把它们分成两组，它们的大小最多只相差一个元素。此外，两组之间的值和的差异应该是最小的。可选地，如果元素个数为奇数且总和不相等，则较小的集合应具有较大的和。

这将是最优解，但我只需要子集大小约束的精确解。和的差不需要严格地是最小的，但应该接近。另外，我希望较小的集合(如果有的话)有较大的总和。

我意识到这可能与分区问题有关，但这并不完全相同，也不那么严格。

我目前的算法如下，但我想知道是否有改进的方法:

arbitrarily divide the set into two sets of the same size (or 1 element size difference)
do
  diffOfSums := sum1 - sum2
  foundBetter := false
  betterDiff := 0.0
  foreach pair of elements from set1 and set2 do
    if |diffOfSums - 2 * betterDiff| > |diffOfSums - 2 * (value1 - value2)| then
      foundBetter := true
      betterDiff := value1 - value2
    endif
  done
  if foundBetter then swap the found elements
while foundBetter

我对这种方法的问题是我不确定实际的复杂性，也不确定它是否可以改进。它当然不能满足让较小的子集有较大的和的要求。

是否有任何现有的算法恰好做我想要实现的?如果不行，你能不能给我一些建议来改进我的算法或者找出它可能已经对这个问题很好了?

Answer 1

很容易证明划分问题在多项式时间内简化为这个问题。

假设你想解决某个数组A的分区问题，但你只知道如何解决这个问题。你只需要将数组长度加倍，用0填充它。如果你能用你的算法解决它，那么你就解决了分区问题。这证明你的问题是NP-hard。

但是你会发现你不能将这个问题简化为分区(即它不是np完全的)，除非你限制浮点数的精度。在这种情况下，同样的算法可以解决这两个问题。

一般情况下，你能做的最好的事情就是回溯。

Answer 2

我的建议是对值进行排序，然后考虑每对值(v1, v2)， (v3, v4)，将每对中的一个元素放入一个分区。

这个想法是交替地将值放入每个集合，所以:

s1 = {v1, v4, v5, v8, . . . }
s2 = {v2, v3, v6, v7, . . . }

如果元素个数为奇数，则将最后一个值放入最符合条件的集合中。

你有一个宽松的最小的定义，所以一个完整的搜索是不必要的。上面的代码应该可以很好地用于许多值的分布。