100分求一算法，在家都来看看。

问题描术：手动输入N个实数A[1]－A[N]，将其分为X,Y,Z三组，使三组中所有数的和尽可能接近。
如：1，2，3，4。X:1＋2＝3;Y:3;Z：4

解决方案 »

免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货

我大致考虑了一个算法，不知对不对，希望对你有所启发^_^
1、找到最大的3个数，分别放到X、Y、Z中；
2、在剩余数中找到最大值，放到X、Y、Z中总和最小的那个组中（如果相等，任意放在一个组）；
3、重复2，直到所有输入的实数都处理完。
楼上的办法不错。不过楼主有一点要搞清楚的是下面哪一个答案更加符合要求：（总数的平均值为23）
数字如下： 1  4  6  10  15  8  25
A: 21 23 25
B: 22 22 25
用楼上的算法更加可能出现的是答案B。
conrad_wan(pineapple)的算法我看了，很有道理，测了一些数据都正确，对于 pweixing(幸运米，幸运得米！) 所说的数据不会出现B答案。谢谢两位关注。！可是我还不能确定是不是一定准确呀。
有没有有能用穷举法得出一个一定正确的结果来，然后可以用来检测其它算法，我实在想不出来怎么样能列举得尽。
事实证明conrad_wan(pineapple)的算法是有问题的，如（1.8,2,2.1,3.7,2.5,2.5,3.4,3.1）
应是：
X:2.5,2.5,2
Y:3.4,3.7
Z：3.1,2.1,1.8
而按此算法：
X:3.7,2.1,1.8
Y:3.4,2.5
Z：3.1,2.5,2
大家都来想想呀，有没有什么办法呀。
of123() ：
当然是要最优解了，数据一般不会大于30个，而且数据也不会很大，所以说速度方面应是可以忍受的，只是要找一个最优解，从我上面那个例子可以看到conrad_wan(pineapple)的算法得出的解果误差还是很大的，如果再加一步，我想的（取和相差最大的两组，交换其中单个数据差小于和差的数据，这样直至找不到为止，应可以求出最优解了吧，可是如何写程序呢，好像很难。）
我考虑了一下:全部为整数情况,其他类似
先把所有数都排序一下
然后把所有数加起来/3  得到每组和的平均趋向值设为E ,然后把所有数分别和E作差,取绝对值
把所有绝对值加起来,除数的个数N,得到平均差值设为F
注意:这个平均趋向值E,可能比你最大的数小,这时候要考虑一下(可能有捷径走);大是普遍情况
把原来排序好的数按从小到大,或者从大到小划段
其分段标准按加起来的和与平均差值和平均趋向值做比较,比如所,你取某一段,现在加起来的和已经比E大了(或者刚好),那么这段就应该到此为止,不要再往该段增数据,而应该设一分段标志(具体做法自己想),最好是从小到大分一下段,也从大到小分一下段
剩下的就是调整,取最优解了,最优解可能有多个
yinweihong(真名:尹伟红)：
首先谢谢你的关注。
但从你说的实在看不出来要如何入手呀。是不是高手说话都比较概括呀。^_^
你前面说的都很明白，也是能想象的。只是有一点，就是你那个平均值F，怎么后边没提到有什么用呀。
对于调整，当然是最重要的了，在我看来此问题之难点就在于如何调整，前期应该有很多方法实现，比如conrad_wan(pineapple)说的方法，经过调整也可能会得出正确的值。但如何调整呢？？？？？如果开始分的组就不是十分合理呢？？？
/////平均值F，怎么后边没提到有什么用
其分段标准按加起来的和与平均差值和平均趋向值做比较即|E-A(n)|在F附近
yinweihong(真名:尹伟红) ：
我也知道“其分段标准按加起来的和与平均差值和平均趋向值做比较即|E-A(n)|在F附近”。
可能是水平问题吧，确实无法把你的算法心领神会，特别是关于后边的“调整”。我总觉得这个调整的过程很难写完全。
能不能用点宝贵时间传个程序上来呀多谢了。^_^
我觉得 conrad_wan(pineapple) 的算法是否可以加强一下
比如对于 2,3,4,20,21,25 这个例子
算法结果是
20,21,25
4         '1
    3      '2
2         '3
________
26,24,25这样算起来的话,26距离平均值多1,现在从跟平均值差的比较多的组中寻找可以互换的数值(或者数值组).
比如上例中,4 和 3 互换
结果就正确了
little_iwf(陀螺):
请不要针对某一个例子来说方法，我个人认为例子只能证明算法不行，却不能证明算法行。^_^
你所说的加强我想过了，（取和相差最大的两组，交换其中单个数据差小于和差的数据，这样直至找不到为止，应可以求出最优解了吧，可是如何写程序呢，好像很难。）但这个过程实现起来好像不怎么容易。