问题描述
这是我的想法，但是我不确定这是否是正确的解决方案：
This is the idea that I have, but I am not sure if this is a correct solution:
- 对数组进行排序
- 取前两个元素。将它们视为2套（每个都有1个元素）
- 从数组中取出下一个元素。
- 决定该元素应进入哪个集合（通过计算总和=>它应为最小值）
- 重复
- Sort the array
- Take the first 2 elements. Consider them as 2 sets (each having 1 element)
- Take the next element from the array.
- Decide in which set should this element go (by computing the sum => it should be minimum)
- Repeat
这是正确的解决方案吗？我们可以做得更好吗？
Is this the correct solution? Can we do better?
推荐答案
版本是问题，它称为。在许多情况下，有许多可以提供最佳的或至少足够好的解决方案。
The decision version of the problem you are describing is an NP-complete problem and it is called the partition problem. There are a number of approximations which provide, in many cases, optimal or, at least, good enough solutions.
您描述的简单算法是游乐场儿童选择团队的一种方式。如果该组中的数字具有相似的数量级，则此的效果非常好。
The simple algorithm you described is a way playground kids would pick teams. This greedy algorithm performs remarkably well if the numbers in the set are of similar orders of magnitude.
文章，由 American Scientist 进行了出色的分析问题。您应该仔细阅读它！
The article The Easiest Hardest Problem, by American Scientist, gives an excellent analysis of the problem. You should go through and read it!
这篇关于如何将一个集合分为两个子集，以使两个集合中的数字之和之间的差异最小？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！