arrays - 将集合分成两组

Question

给定一组元素。您必须将它们分成两组，以使单个组的元素总和之间的差异最小。

例子:

5
4 6 7 2 1

两个组是:{4,6} 和 {7,2,1}。

我的方法:我只遇到过这个问题的蛮力解决方案，即使用位移技术生成该集合的所有子集 (2^n)。

我正在寻找更好的解决方案。

Answer 1

我不会给你解决方案，而是给你两个提示:

1. 计算所有元素的总和，而不是解决原始问题。表示此 S。解决如下问题 - 找到给定数字的子集，其总和不超过 S/2。剩余的数字将构成另一个子集。

2. 我上面描述的问题非常简单knapsack problem所有元素的成本相同。同样可以使用 dynamic programming 解决(但在这种情况下，它将比用于经典背包问题的方法简单得多)