将一组值划分为两个大小相同或相似且总和相似的值

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

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

想法是将值交替放入每个集合中，因此：

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

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

您对“最小值”有一个宽松的定义，因此不需要完整搜索。上面的方法对于值的许多分布应该很好地工作。