如何将一个集合分为两个子集，以使两个集合中的数字之和之间的差异最小？ [英] How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?

问题描述

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

Given a set of numbers, divide the numbers into two subsets such that difference between the sum of numbers in two subsets is minimal.

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

This is the idea that I have, but I am not sure if this is a correct solution:

1. 对数组进行排序


2. 取前两个元素。将它们视为2套（每个都有1个元素）


3. 从数组中取出下一个元素。


4. 决定该元素应进入哪个集合（通过计算总和=>它应为最小值）


5. 重复

1. Sort the array
2. Take the first 2 elements. Consider them as 2 sets (each having 1 element)
3. Take the next element from the array.
4. Decide in which set should this element go (by computing the sum => it should be minimum)
5. Repeat

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

Is this the correct solution? Can we do better?

推荐答案

决定版本是 NP完整问题，它称为 分区问题 。在许多情况下，有许多近似值可以提供最佳的或至少足够好的解决方案。

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!

这篇关于如何将一个集合分为两个子集，以使两个集合中的数字之和之间的差异最小？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！