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

问题描述

<块引用>

给定一组数字，将这些数字分成两个子集，使得两个子集中的数字之和之间的差异最小.

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

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

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

解决方案

decision 版本您描述的问题是 NP-complete 问题，称为 分区问题.有许多近似值，在许多情况下，它们提供了最佳的或至少足够好的解决方案.

您描述的简单算法是游乐场孩子们挑选球队的一种方式.如果集合中的数字具有相似的数量级，则此贪婪算法的性能非常好.>

文章最简单最难的问题，由美国科学家提供，对该问题进行了出色的分析.你应该通读一遍！

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. 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?

解决方案

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.

The article The Easiest Hardest Problem, by American Scientist, gives an excellent analysis of the problem. You should go through and read it!

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