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

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

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

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

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

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

您对 minimal 的定义比较宽松，因此无需进行全面搜索。以上对于值的许多分布应该工作得很好。

Answer 2

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

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

但是你会发现你不能将这个问题简化为分区（即它不是 NP 完全的），除非你限制你的浮点数的精度。在那种情况下，相同的算法将同时解决这两个问题。

在一般情况下，最好的办法就是回溯。

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

Divide set of values into two sets of same or similar size with similar value sums

algorithm

partition-problem