如何将一个集合分为两个子集，以使两个集合中的数字之和之间的差异最小？

• Z时代
• 2024-01-10
• 分类：问答

给定一组数字，请将数字分为两个子集，以使两个子集中的数字总和之间的差异最小。

这是我的主意，但是我不确定这是否是正确的解决方案：

1. 对数组排序
2. 取前两个元素。将它们视为2套（每个都有1个元素）
3. 从数组中获取下一个元素。
4. 决定该元素应该进入哪个集合（通过计算总和=>它应该是最小值）
5. 重复

这是正确的解决方案吗？我们可以做得更好吗？

回答：

您描述的问题的决策版本是NP完全问题，称为 分区问题

。在许多情况下，有许多近似值可以提供最佳或至少足够好的解决方案。

您描述的简单算法是游乐场儿童选择团队的一种方式。如果集合中的数字具有相似的数量级，则该贪婪算法的性能会非常好。

文章

最简单的最困难的问题 ，由 美国科学家 ，给出了问题的一个很好的分析。您应该阅读并阅读！

以上是 如何将一个集合分为两个子集，以使两个集合中的数字之和之间的差异最小？ 的全部内容， 来源链接： utcz.com/qa/421721.html