1

所以我实际上打算用它在 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 中实现最终产品。

谢谢！

编辑

我喜欢目前介绍的两种方法（感谢chechen 和 sumudu fernando），这两种方法都提供了快速实现接近（或完全）理想答案的好方法。对于足够小的整数集，我想你可以强行计算并明确地说特定的答案是最好的（或并列最好的）。做这样的事情有什么建议吗？换句话说，一种以可能很慢（或对于大型问题集完全不可行）为代价来保证理想答案的方法。

4

1 回答 1

1
  1. 计算所有元素的总和。
  2. 计算总和的一半，s。
  3. 将背包问题应用于求和的数字s。
  4. 将溶液放入一个容器中，其余元素放入另一个容器中。
于 2012-10-03T01:50:44.490 回答