algorithm - 将一组值分成两组具有相似值和的相同或相似大小

Question

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

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

我意识到这可能与 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

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

是否有任何现有算法恰好可以实现我想要实现的目标？如果没有，您能否建议我改进算法或找出它可能已经相当适合解决问题的方法？

Answer 1

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

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

但是您会发现您无法将此问题简化为分区(即它不是 NP 完全问题)，除非您限制 float 的精度。在那种情况下，相同的算法将同时解决这两个问题。

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