0

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

那将是最佳解决方案，但我只需要子集大小约束的精确解决方案。总和的差异并不需要非常小，但应该接近。我也希望较小的集合（如果有）具有较大的总和。

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

我目前的算法如下，但我想知道是否有办法改进它：

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

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

是否有任何现有算法恰好可以实现我想要实现的目标？如果没有，你能建议我改进我的算法或找出它可能已经对这个问题有相当好的效果吗？

4

2 回答 2

3

It easy to prove that the partition problem reduces to this problem in polynomial time.

Imagine you want to solve partition for some array A, but you only know how to solve your problem. You just have to double the array length, filling it with zeros. If you can solve it with your algorithm, then you have solved the partition problem. This proves your problem to be NP-hard.

But you'll see you can't reduce this problem to partition (i.e. it isn't NP-complete), unless you limit the precision of your floats. In that case the same algorithm would solve both.

In the general case, the best you can do is backtrack.

于 2015-08-22T17:41:14.693 回答
2

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

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

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

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

您对最小的定义很宽松，因此无需进行完整搜索。以上对于值的许多分布应该工作得很好。

于 2015-08-22T15:47:04.773 回答