algorithm - 将数字均匀分配到组中的最佳策略

Question

您有两个整数列表 A={1,3,60,24} 和 B={14,54,3}，顺序和列表长度未确定。将 A 中的数字放入 B 以使 B 中结果的方差尽可能平衡的最佳策略是什么。如果没有可用空间，则不必将 A 中的所有数字都放入 B 中。但如果有可用空间，则必须输入数字

我正在考虑应用 Branch and Bound，但是，我不确定如何找到剪枝条件，例如计算子问题(未完全填充)的方差来判断要剪掉哪个分支？

有什么想法吗？

Answer 1

您描述的问题是分区问题(http://en.wikipedia.org/wiki/Partition_problem)。寻找最佳解决方案是 NP 完全的，但是有许多近似值对于大多数情况来说几乎是完美的。

事实上，您描述的算法是 Playground 上 children 挑选团队的方式。如果集合中的数字具有相似的数量级，则这种贪心算法的性能非常好。当然，这不是最好的解决方案，但考虑到问题是 NP 完全的，它的简单性真是太棒了。

美国科学家中的这篇文章对问题进行了出色的分析，您应该通读并阅读它:最简单的难题 (http://www.americanscientist.org/issues/pub/2002/3/the-easiest-hard-problem)。