在Swift中将CGFloat数组分解为n个近似相等的子数组,保持顺序

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

这将是最佳解决方案,但我只需要一个关于子集大小约束的精确解决方案。严格来说,总和的差异不一定是最小的,但应该接近。此外,我更希望较小的集合(如果有的话)具有较大的总和。

我意识到这可能与 partition problem ,但并不完全相同,也不那么严格。

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

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

我对这种方法的问题是,我不确定实际的复杂性以及是否可以改进。它当然不能满足将较小的子集留给较大的总和的要求。

是否有任何现有的算法恰好能实现我想要的目标?如果没有,你能给我建议一些方法来改进我的算法,或者弄清楚它可能已经对这个问题相当好了吗?