1

Given is a set of elements. You have to divide them into groups of two, such that the difference between the sum of elements of an individual group is minimum.

example:

5
4 6 7 2 1

two groups are: {4,6} and {7,2,1}.

My approach: I have come across only the brute force solution of this problem, i.e. generate all the subsets (2^n) of the set using bit shifting technique.

I am looking for a better solution.

4

1 回答 1

2

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

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

  2. 我上面描述的问题是非常简化的背包问题，所有元素的成本相同。同样，它可以使用动态编程来解决（但在这种情况下，它比用于经典背包问题的方法简单得多）

于 2013-03-05T07:30:39.127 回答