将元素放入容器并保持容器尽可能均匀的良好排序算法是什么?



所以我实际上打算用它在ExtJS4中进行一些动态表单布局生成,但我认为我可以简化问题以便于讨论而不会丢失任何东西:

假设我有一个整数列表,我想把它放在两个容器中。完成后,我希望两个容器都"尽可能均匀",在这种情况下,这意味着每个容器内的整数之和尽可能接近。在这种情况下,每个容器中最终有多少整数并不重要,只要它们的和很接近即可。

下面是一个可能的输入和理想输出的例子:

Integers: [1,7,13,3,6,8]
Container A: [13,6] (sum 19) 
Container B: [1,7,3,8] (sum 19)

一种简单的方法可能是在整数列表上迭代一次,并将每个整数放在当前具有较小和的容器中:

Integers: [1,7,13,3,6,8]
Container A: [1,13,8] (sum 22)
Container B: [7,3,6] (sum 16)

你们建议用什么算法/方法来解决这个问题?我想有很多潜在的。如果您发现在代码示例中更容易思考,我将用javascript实现最终产品。

谢谢!


编辑

我喜欢迄今为止提出的两种方法(感谢chacken和sumudu fernando),这两种方法都提供了快速实现接近(或确切地)理想答案的好方法。对于一组足够小的整数,我想你可以强行进行计算,并明确地说特定的答案是最好的(或并列为最好的)。有什么建议可以做这样的事情吗?换句话说,一种以可能缓慢(或对于大型问题集完全不可行)为代价来保证理想答案的方法。

  1. 计算所有元素的总和
  2. 计算总和的一半,s
  3. 将背包问题应用于使目标和为s的数
  4. 将溶液放入一个容器中,其余元素放入另一个容器

相关内容

  • 没有找到相关文章

最新更新