将一组值划分为两个大小相同或相似且总和相似的值 [英] Divide set of values into two sets of same or similar size with similar value sums

问题描述

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

I have a set of floating point values that I want to divide into two sets whose size differs at most by one element. Additionally, the difference of value sums between the two sets should be minimal. Optionally, if the number of elements is odd and the sums cannot be equal, the smaller set should have the larger sum.

那将是最佳解决方案，但我只确实需要针对子集大小约束的精确解决方案。严格来说，总和之差不必极小，但应接近。我也希望较小的集合（如果有）具有较大的总和。

That would be the optimal solution, but I only really need an exact solution on the subset size constraints. The difference of sums doesn't strictly need to be minimal, but should come close. Also I would prefer if the smaller set (if any) has the larger sum.

我意识到这可能与分区问题，但它并不完全相同，也没有那么严格。

I realize this may be related to the partition problem, but it's not quite the same, or as strict.

我当前算法如下，但是我想知道是否有一种方法可以对此进行改进：

My current algorithm is the following, though I wonder if there's a way to improve upon that:

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

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

My problem with this approach is that I'm not sure of the actual complexity and whether it can be improved upon. It certainly doesn't fulfill the requirement to leave the smaller subset with a larger sum.

是否有任何现有算法恰好可以实现我想要实现的目标？如果不是这样，您能否建议我改善算法或弄清楚它可能已经很好地解决了问题？

Is there any existing algorithm that happens to do what I want to achieve? And if not, can you suggest ways for me to either improve my algorithm or figure out that it may already be reasonably good for the problem?

推荐答案

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

My suggestion would be to sort the values, then consider each pair of values (v1, v2), (v3, v4) putting one element from each pair into one partition.

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

The idea is to alternate putting the values into each set, so:

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

如果元素数量奇数，请将最后一个值放入最能满足您的条件的集合

If there are an odd number of elements, put the last value into the set that best meets your conditions.

您对最小值有一个宽松的定义，因此无需进行全面搜索。上面的代码对于许多值分布都应该很好用。

You have a relaxed definition of minimal, so a full search is unnecessary. The above should work quite well for many distributions of the values.

这篇关于将一组值划分为两个大小相同或相似且总和相似的值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！