求一算法～

Question

需求：
有n个数 例如 98，43，20，89，11，129，20 ....
把这些数分成2组，希望2组的数字之和的比值最接近于1

Answer 1

求组合：x从1个直到n/2的组合，求出一个组合，把余下的n-x个的数求合，再求比值。
这个是比较笨的办法

Answer 2

先得出 n 个数的和 得到sum；
做个循环把所有的数换着顺序相加 得到 totle, 每加一次做判断totle < sum/2 + 1 || totle < sum/2 - 1) && (sum - totle < sum/2 + 1 || sum -totle < sum/2 - 1)
   

Answer 3

先求出n个数的和sum,取中间值middle=sum/2,
然后对n个数排序, 先取n个数中的最大的一个max,判断它是否小于middle,否就可以分组了;是就求出temp=middle-max,在余下的数据中寻找和等于或接近temp的数据(中间设一个最小数组min[]用于保存两组中的最小差值,如果差值为0，就可以分组),用同样的方法,不过判断的时候是判断它是否小于temp,如此穷举.
如果min[]中没有为0的,则寻找min中最小的值(绝对值最小的),通过相关方法即可找出比值最小的组合.

Answer 4

第一感觉np问题
大家可以先观察下相对简单一点的一个问题
在题目中加个限制条件，
数组为2n个，分成两组每个为n
那么这个题就是编程之美上面的某题，
原书中给了一个动态规划算法
时间复杂度为O(n^2*sum)
其中sum为数组的和
题目给的条件太宽松了
枚举＋深度优先搜索估计可行（在数组全是正数的前提下）
先假设一个组是1 另一个组是n-1
枚举之
然后一个组是2 另一个组是n-1
继续枚举，其间用深搜穷举出所有的和
找出最接近sum/2的就行
时间复杂度初步估计为1!+2!+..+[n/2](取整)!
一看估计就是np问题
杯具了
动态规划估计有更好的办法，不过我没仔细想
编程之美上的那个就是用动态规划做的，哈哈

Answer 5

步骤如下：
1.先将原集合按照由大到小的顺序进行排序。
2.然后再将集合内的数字进行划分。划分方法如下：
（1）为每个组创建一个sum变量，保存该组的数字之和。
（2）每次添加新数字，都会将数字的值，累计到sum变量中。
（3）每次划分的策略，都是：从原集合中取出一个数字，添加到sum变量较小的分组中去。
（4）如果两个分组的sum值相等，则，添加到第一个分组中去。
（5）重复（2~4）步骤，直到原集合中没有数字。
3.理论依据：
两个分组的和的比值近似为1 ，说明，两个和要尽量相等。
对分组和的影响较大的因素，是原集合中数值较大的数字。
所以，划分数字，要采用先大后小的策略，
因为，较小的数字，对分组和的影响较小，
以保证后面的划分，使得两个分组和的值，趋向近似相等。

Answer 6

圆满 NPC问题，没有多项式解法，近似算法可参考http://blog.csdn.net/rcfalcon/archive/2010/04/06/5454994.aspx 感谢