时间:2008-08-27 23:01:32   来源:论坛整理  作者:  编辑:chinaitzhe

把一个数组分成指定的组数，在优先考虑子数组个数接近的情况下，各组的和最接近。
如{1,2,3,4,5,6}分2组，符合条件的2个数组{2,3,5}{1,4,6}
如{1,2,3,4,5,6}分3组，符合条件的3个数组{1,6}{2,5}{3,4}
如{1,2,3,4,5,6,7}分2组，符合条件的2个数组{1,2,4,7}{3,5,6}
返回所有最佳分法。

当然数组不都是这么简单的……所以我搞不定，呵呵，请帮帮忙……
网友回复:穷举去吧
网友回复:提供一个简单的算法，可能并不完美
1. 将数组排序
2. 假定将数组分为N组
3. 那么1, N 1, 2N 1, ...是一组
2, N 2, 2N 2, ...是一组
...
N, 2N, 3N, ... 是一组
网友回复:给你一个思路步骤：
1、给数组按大小排序
2、算出总和
3、算出平均值，也就是每一个小组的和
4、根据大数组是否整除小数组、平均值是否是整数做一个判断，因为已经排序，所以只需要头尾取值
具体程序你自己写吧！

网友回复:我想是不是可以这样考虑：
一、把要分的数组排序。
二、根据指定的数组数将原来的数组分成小组。
三、将各个小组组成各个小的数组。
可能我说的不太明白，给大家举例一下：
比如：{8,7,6,5,4,3,2,1}（排好序的数组,建议由大到小排序）
现在要分3组：我们记录如下：876、543、210 其中0是我们虚拟的一个数字，便于每个小组3个数字。为了便于理解，我们把上面的数字写成如下：
8 7 6
5 4 3
2 1 0

然后组成小的数组就是{8,4,0}{7,3,2}{6,5,1}也就是取值按照向右下查询的方法，如果右下查询未，到下一行的第一位取值。
最后别忘记把我们开始的那个虚拟的0去掉。

如果有问题，请联系我 Javado@163.com 大家共同探讨
网友回复:谢谢各位，不过我举的例子只是最简单的情况，是等差数组，如果数组不等差就不能用了，
如数组{1,5,16,17,18,30,31,33}按照JadoNet的做法

列矩阵为：

33 31 30
18 17 16
05 01 00

结果为：
33,17,00 ==50
31,16,05 ==52
30,18,01 ==49

显然不如一下这种分法好：
33,17,00 ==50
30,16,05 ==51
31,18,01 ==50

请大家帮帮忙，谢谢。
网友回复:ProvidenceZY的方法似乎可行，试试先。
网友回复:还是不行…………
网友回复:只要能找出一种最佳的分法，其他的应该就可以找到，找出该分法中各等长分组内和值相等的子数组（就是分组后的子数组的子数组）进行交换。
网友回复:确实，我说的方法是有问题，哈哈

能不能按照我的方法分开之后，然后在匹配最大和与最小和的差，如果这个差 比 数组中最任意两个数字的差小，说明正确，否则再次分析查找。

我只是一个想法，不知道能否实现，此贴关注中...
网友回复:mark~
网友回复:study
网友回复:不好分,因为数字个数不确定,而且组数也不确定.
例如:{1,5,16,17,18,30,31,33}分5组.

网友回复:这问题满难的~哦
网友回复:有难度。。。。
网友回复:to:lmx8757921
每组个数不一定要相等，但是要接近，如你举的{1,5,16,17,18,30,31,33}分5组。
因为8/5=1...3，所以最接近的分法是5组中，2组是1个元素，其他3组两个元素。
至于各组的和最接近，可以用标准差判断。


网友回复:帮顶，学习中~~~
网友回复:有难度，，不过分组的话，要么各组内的元素数相等，要么差一，我只是个人觉得这样
网友回复:算法如下：
1： 算平均值
2： 排序
3： 所有大于平均值的数单独一组，并从原始排序队列删除；

下面开始分组
4：建立一个空的临时组
5：把剩下的最大数加入临时组，计临时组数和，算出和平均值之差
6：从剩下的数中找出相加值最接近5中计算的差的组合，加入临时组。
7：临时组加入正式分组，并把其成员从原始排序队列删除。
8：重复上面步骤，直到组数=需要分的组数-1， 剩下的所有数为一组。


这样，原算法就转换为：

从数组中找出其和最接近某一个数值的组合，这个应该简单多了8？
网友回复:to:jihanzhong

这样也不适合，因为前提是优先考虑子数组个数接近，
如sling2007说的那样“要么各组内的元素数相等，要么差一”
比如{-1,-1,-1,-1,2,2,2}分2组，两个比平均值大的2已经把组数满足了。

网友回复:o? 没考虑负数
网友回复:那就这样,算法如下：

1： 算平均值
开始分组
2：建立一个空的临时组
3：从剩下的数中找出相加值最接近平均值的组合，加入临时组。
4：临时组加入正式分组，并把其成员从原始排序队列删除。
5：重复上面步骤，直到组数=需要分的组数-1， 剩下的所有数为一组。

网友回复:不好意思，刚才可能表述不清楚，应该是优先考虑子数组元素个数接近。
大家帮帮忙吧~~
网友回复:to:jihanzhong

{1,2,3,4,5,6,7,20}
分3组，平均值16
按你的分法
{20,1}
{3,6,7}
{2,4,5}
方差16.7

不如这个好
{20,1}
{3,5,6}
{2,4,7}
方差12.7
网友回复:"优先考虑子数组元素个数接近"

那么LZ的问题可以转化为：
把n*M个数平均分成n组，要求各组的和最接近！

网友回复:顶个先
网友回复:没有确定解法的，建议用GA


网友回复:to:a0002
谢谢，优先考虑子数组元素个数接近，不一定相等，但各子数组的长度之差不大于1。

用GA？能给个代码么？
网友回复:优先考虑子数组元素个数接近，不一定相等，

但分组的结果是：各子数组的长度之差不大于1。

所以，给少一个数的组后面添加一个虚的0,不影响结果!
网友回复:嗯，是的。
网友回复:嗯，那问题就转化为你说的：
把n*M个数平均分成n组，要求各组的和最接近了。

就相当于把原数组用0补到长度可以被组数整除，然后分成N组，每组至多含一个0。
网友回复:关注
网友回复:给你一个思路步骤：
1、给数组按大小排序
2、算出总和
3、算出平均值，也就是每一个小组的和
4、根据大数组是否整除小数组、平均值是否是整数做一个判断，因为已经排序，所以只需要头尾取值 注意的几个条件你给把握好了，应该可以满足你的条件
网友回复:我也给你一个思路步骤：
1、将数组排序
2、算出总和
3、用总和除以分数组的个数,得余数和商.
4、再将商与数组中的最大值相比,
if(商比最大值大)
那就将数组中的数按这个值组合分组
else(商小于等于最大值)
就将大于商的分在一组
5,按这思路应该能解决问题
12,15,20,35,45,60,50,70---商102余1,
组合102-{70,20,12},105--{60,45},100--{50,35,15}
{1,2,3,4,5,6,7,20}
{20},{1,6,7},{2,3,4,5}
网友回复:不知道有没有好的算法，用排列组合直接算应该是可以的，就是慢了点儿

网友回复:studying.....
网友回复:如{1,2,3,4,5,6}分2组，符合条件的2个数组{2,3,5}{1,4,6}
如{1,2,3,4,5,6}分3组，符合条件的3个数组{1,6}{2,5}{3,4}

哪个算是最优分法？
网友回复:没有规律啊,似乎比较难!考虑中.....
网友回复:我觉得很简单啊，
先排序，然后，首尾相加，第二个跟倒数第二个相加，依次类推。。。。。
网友回复:好像很难,就算是等差数组,不用jadonet的方法的话,
{1,2,3,4,5,6,7,8,9}怎么分成{9,5,1,},{8,4,3},{7,6,2}?
网友回复:

Java code

Code highlighting produced by Actipro CodeHighlighter (freeware)

http://www.CodeHighlighter.com/



谢谢各位，不过我举的例子只是最简单的情况，是等差数组，如果数组不等差就不能用了， 

如数组{1,5,16,17,18,30,31,33}按照JadoNet的做法 



列矩阵为： 



33   31   30 

18   17   16 

05   01   00 



结果为： 

33,17,00     ==50 

31,16,05     ==52 

30,18,01     ==49 



显然不如一下这种分法好： 

33,17,00     ==50 

30,16,05     ==51 

31,18,01     ==50 



请大家帮帮忙，谢谢。

是否可以先用jadonet的方法得出:
33,17,00 ==50
31,16,05 ==52
30,18,01 ==49
再进行优化.比如将每个小组的和进行排序:
31,16,05 ==52
33,17,00 ==50
30,18,01 ==49
然后比较最大和数组&最小和数组的差:52-49=3
寻找这两个数组中对应元素差值小于3大于0的元素交换.
比如:31-30=1 小于3,大于0,就是说31和30 这两个元素可以交换.
17-18=-1 小于0,不能交换.
05-01=4 大于3,不能交换.


自己的一点看法.
网友回复:to:ProvidenceZY
谢谢你再来看，不过你说的比较抽象，比如当大数组不整除小数组时该怎么处理比较好呢，
头尾取值的话，如果取的是奇数个，最后一个要从头取还是尾取呢？
网友回复:to:fghshy

if(商比最大值大)
那就将数组中的数按这个值组合分组
else(商小于等于最大值)
就将大于商的分在一组

不好意思，不理解你的意思，“就将大于商的分在一组”那么不是那组会很大么？
或者你的意思是每个大于商的分一组？那如果大于商的元素个数多于要分的组数呢？


网友回复:to:IOPsyche

jadonet的方法应该和二楼usherlight所要表达的方法一样。

你的方法可能在特定的数组很有效，不过要通用应该比较难，

比如{1,2,3,4,5,6,7,20}
排3组，均值16

按jadonet的方法

20,07,06
05,04,03
02,01,00

20,04,00 ==24
07,03,02 ==12
06,05,01 ==12

最大和数组&最小和数组的差：24-12=12

有两个最小的，而且每个最小的数组中的每个值都小于12。应该怎样选择呢。


难道只有暴力……
网友回复:是不是可以使用聚类算法，比如K-Means等
分类的标准就是和小于一个定值
网友回复:路过
网友回复:两个问题一样
http://topic.csdn.net/u/20071121/13/eb66d013-3fd9-4791-9dbf-348c5c183317.html
网友回复:呵呵，同一个帖子，问题当然一样咯，地址也是一样的……
网友回复:关注中!
网友回复:好难办啊~!关注~!
网友回复: 找两个数学教授肯定就好办了.
网友回复:a0002应该是想说跟我一样的问题吧,确实是差不多~~~
http://topic.csdn.net/u/20071121/23/94521e31-7c32-4d62-83eb-0f36728da2b1.html
网友回复:这个题目是不是个背包问题啊，NP hard。。。。
用贪心算法，求近似解吧。。。
如果输入规模比较小可以穷举
网友回复:to:zsl448
确实差不多。目前看到的应该就是2楼要表达的那种方法比较好了。
网友回复:先排序，然后一个一个分
网友回复:zsl448提到的帖子里一楼的方法好像更好，研究下。
网友回复:谢谢各位，结贴了。有更好的方法欢迎提供……
网友回复:MARK
网友回复:hao
网友回复:我想问一下，如果数据的个数确定（18个），分组数也确定（4组或6组），而且数组里的数值偏差不会太大（最大值与最小值的差在3.00以内）， 有什么排列思路？？给点建议！