logo标签列表

将值均匀分成组

algorithmsorting
11

让我尽力解释这个情况。

假设我有3个值

1, 2, 3

我告诉一个算法将这些值分成x列，假设 x = 2 以便更清楚地说明。

该算法确定这组值最好的方式是将其放入两列中，如下所示。

1st column    2nd column
---------------------------
1             3
2

每列都有偶数个值（总数，不是字面量）。

现在假设我拥有以下这些值：

7, 8, 3, 1, 4

我告诉算法我想要将值分成3列。现在算法告诉我以下是最佳匹配。

1st column    2nd column    3rd column
8             7             3
              1             4

注意列并不完全相等，但尽可能接近平均分布。稍微多一点或少一点都是可以接受的，只要列表尽可能接近平均。

有人有建议吗？知道如何做到这一点的好方法吗？

3个回答
6
4
如果您想要完全相同的值，对于列数x=2，这是经典的分割问题，它是NP-完全问题，但有伪多项式解决方案。
任何更多的列（即x>2），它就会变成强NP-完全问题。 3分割问题。
对于x>3，我怀疑它仍然是强NP-完全问题。
由于x分割问题可以归约为您的问题，因此它将与上述问题一样困难。
您可能需要一些启发式方法来帮助您。
4

我之前回答过类似的问题。

我能想到一种贪心次优解决方案。

  1. 按降序排序数字。（较小的数字影响较小，所以稍后处理）
  2. 确定你要拥有的集合数量。不太确定这个
  3. 逐个遍历集合元素，并将它们放入具有最低总和的子集中（在相等的情况下轮流进行）

然而，这永远不会给你最优的解决方案。

对于你的情况，8 7 4 3 1 将是顺序。你将（幸运地）得到与你提到的相同的结果。

8 = 8

7 1 = 8

4 3 = 7

这并不总是会给你最优的解决方案。

这是一个非常棒的启发式解决方案，避免了使用任何调整参数，并且编程非常容易。在迭代较小的元素子集上使用背包算法会冒着将许多大元素留到最后的风险，而且实现起来似乎很麻烦。这种方法看起来更加健壮。 - John Haberstroh
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接