一尘不染

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

algorithm

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

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

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

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


阅读 723

收藏
2020-07-28

共1个答案

一尘不染

您描述的问题的决策版本是NP完全问题,称为 分区问题
。在许多情况下,有许多近似值可以提供最佳或至少足够好的解决方案。

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

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

2020-07-28