给定一组数字,请将数字分为两个子集,以使两个子集中的数字总和之间的差异最小。
这是我的主意,但是我不确定这是否是正确的解决方案:
这是正确的解决方案吗?我们可以做得更好吗?
您描述的问题的决策版本是NP完全问题,称为 分区问题 。在许多情况下,有许多近似值可以提供最佳或至少足够好的解决方案。
您描述的简单算法是游乐场儿童选择团队的一种方式。如果集合中的数字具有相似的数量级,则该贪婪算法的性能会非常好。
文章 最简单的最困难的问题 ,由 美国科学家 ,给出了问题的一个很好的分析。您应该阅读并阅读!