把一个数组分成指定的组数,在优先考虑子数组个数接近的情况下,各组的和最接近。
如{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,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, ... 是一组
一、把要分的数组排序。
二、根据指定的数组数将原来的数组分成小组。
三、将各个小组组成各个小的数组。
可能我说的不太明白,给大家举例一下:
比如:{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去掉。如果有问题,请联系我 [email protected] 大家共同探讨
如数组{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请大家帮帮忙,谢谢。
每组个数不一定要相等,但是要接近,如你举的{1,5,16,17,18,30,31,33}分5组。
因为8/5=1...3,所以最接近的分法是5组中,2组是1个元素,其他3组两个元素。
至于各组的和最接近,可以用标准差判断。
如sling2007说的那样“要么各组内的元素数相等,要么差一”
比如{-1,-1,-1,-1,2,2,2}分2组,两个比平均值大的2已经把组数满足了。
分3组,平均值16
按你的分法
{20,1}
{3,6,7}
{2,4,5}
方差16.7不如这个好
{20,1}
{3,5,6}
{2,4,7}
方差12.7
把n*M个数平均分成n组,要求各组的和最接近!
谢谢,优先考虑子数组元素个数接近,不一定相等,但各子数组的长度之差不大于1。用GA?能给个代码么?
把n*M个数平均分成n组,要求各组的和最接近了。 就相当于把原数组用0补到长度可以被组数整除,然后分成N组,每组至多含一个0。
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}
{1,2,3,4,5,6,7,8,9}怎么分成{9,5,1,},{8,4,3},{7,6,2}?
如数组{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,不能交换.
自己的一点看法.
谢谢你再来看,不过你说的比较抽象,比如当大数组不整除小数组时该怎么处理比较好呢,
头尾取值的话,如果取的是奇数个,最后一个要从头取还是尾取呢?
那就将数组中的数按这个值组合分组
else(商小于等于最大值)
就将大于商的分在一组 不好意思,不理解你的意思,“就将大于商的分在一组”那么不是那组会很大么?
或者你的意思是每个大于商的分一组?那如果大于商的元素个数多于要分的组数呢?
排3组,均值16按jadonet的方法20,07,06
05,04,03
02,01,0020,04,00 ==24
07,03,02 ==12
06,05,01 ==12最大和数组&最小和数组的差:24-12=12有两个最小的,而且每个最小的数组中的每个值都小于12。应该怎样选择呢。
难道只有暴力……
分类的标准就是和小于一个定值
http://topic.csdn.net/u/20071121/13/eb66d013-3fd9-4791-9dbf-348c5c183317.html
http://topic.csdn.net/u/20071121/23/94521e31-7c32-4d62-83eb-0f36728da2b1.html
用贪心算法,求近似解吧
如果输入规模比较小可以穷举
确实差不多。目前看到的应该就是2楼要表达的那种方法比较好了。