高分寻求一个分班的算法 - CSDN论坛 - CSDN.NET --> 首页 论坛帮助 论坛牛人 论坛地图 CSDN > CSDN论坛 > .NET技术 > C# 管理菜单 置顶 推荐 锁定 移动 编辑 删除 帖子加分 帖子高亮 结帖 发帖 回复 hahahoo 高分寻求一个分班的算法 [问题点数：100分，结帖人hahahoo] 不显示删除回复 显示所有回复 显示星级回复 显示得分回复 只显示楼主 收藏 hahahoo hahahoo 等级： 结帖率：97.56% 楼主 发表于： 2006-10-18 09:34:11 若干个学生进行入学考后，获得语文、数学、英语三门课的分数，要求按照分数平均将这些学生分班（如4个班），分班后要求4个班的总分平均分、各单科的平均分基本相等。 研究了半天，也没有想出一个简单有效的算法。 请各位帮忙出出主意。 分享到： 更多 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 回复次数：41 aafshzj aafshzj 等级： 结帖率：92.86% #1 得分：30 回复于： 2006-10-18 09:51:08 基本思路如下： 1）建立4个队列，每个队列对应一个班，每个队列都记录其当前的各门课程的总分数 2）把所有学生按总分从高到低排序（这一步不是绝对需要的，但是我们希望先把大粒度的学生排掉，再排小粒度，这样容易平）形成学生队列。 3）从学生队列中取出一个学生，计算四个班级的各科平均分，以及四个班级各科分数与平均分数的差值（有正负），谁的各科差值累加最小（考虑正负），就将该学生分到哪个班级。 4）重复3)直到所有学生分配完毕。 这大体应该可以满足你们的要求了。算法本身应该还是可以优化的。 欢迎大家来我的博客作客：http://blog.csdn.net/aafshzj/ 我正在写一系列关于AAF组件框架的文章。该框架能对开发工作提供很多帮助，并极大地提高开发效率。希望大家看一看并提出宝贵建议。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 woshibai112 woshibai112 等级： 结帖率：100% #2 得分：0 回复于： 2006-10-18 10:10:02 up 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 xingyaohua xingyaohua 等级： 结帖率：93.75% #3 得分：0 回复于： 2006-10-18 10:11:17 up 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 hahahoo hahahoo 等级： 结帖率：97.56% #4 得分：0 回复于： 2006-10-18 10:18:21 先谢谢你的思路 你的意思是每提取一个学生准备分班前 1.先计算当时点的每个班级的已分班学生的各科平均分 2.拿该学生的分数与算出来的每个班级的各科平均分计算差值 3.选择最小差值的班级 然后再重复1-3 我这样理解对吗 但是这样做的话，能实现分班后的每个学生的总分平均分也相等吗？ 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 hahahoo hahahoo 等级： 结帖率：97.56% #5 得分：0 回复于： 2006-10-18 10:22:48 有了新想法，其实可以把总分看做一个单独的科目，这样只要做的4门科的平均分一致就可以了 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 diandian82 diandian82 等级： 结帖率：100% #6 得分：0 回复于： 2006-10-18 10:24:46 总分平均分、各单科的平均分基本相等。 如果都要考虑的话，是有点难度。继续关注。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 fd7893 fd7893 等级： 结帖率：100% #7 得分：30 回复于： 2006-10-18 10:27:27 0.设定一个可接受的差距范围； 1.对源队列排序； 2.新建4个队列，赋值：4个队列的偶数列用源队列正向赋值，奇数列反向赋值。比如： 队列号 队列下标1[源队列下标] 队列下标1[源队列下标] …… 1 0[0] 1[7] …… 2 0[1] 1[6] …… 3 0[2] 1[5] …… 4 0[3] 1[4] …… 这样赋值后4个队列的差距应该就不大了。 3. 根据4个队列的差距，正向(就是从小到大)调换各个队列的元素，直到差距小于设定差距时 完成调整。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 Qim Qim 等级： 结帖率：100% #8 得分：10 回复于： 2006-10-18 10:30:41 思路： 1：按总分从低到高把学生进行排序 2：按照1,2,3,4 5,6,7,8 9,10,11,12 .......... 进行分配。 3：把1，4两个班再进行1，2步操作，只是2的操作变成分两个班了。 基本会平衡，且简单可行。因为高分和底分的学生不会很多。我们以前就是如此分的。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 aafshzj aafshzj 等级： 结帖率：92.86% #9 得分：0 回复于： 2006-10-18 10:31:29 hahaoo: 你的理解基本是对的。 其实在两个假设任意之一下这个算法应该都汇市比较平均的： 1）大多数人，学习成绩好的，每门都会比较好，反之亦然。 2）每个人每门课程都是随机的。 因为大体而言，每次都是考虑了三门课程各自的差值（涨落的），所以效果应该还是可以的。其实一个优化实在第3步（此时可以省略第2）步），你不是按顺序去一个，而是取一个成绩涨落最接近课程涨落的学生。这样复杂点，效果是不是很好，还很难说，有兴趣你可以试一下。我前面给出的算法，你可以实测一下，平均分差别应该很小，而且很好地满足了各班希望尖子生随机分配的愿望（为了提高随机性，你可以把4个班分配一次看成一轮，每一轮开始的班级可以随机产生，滚动进行）。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 aafshzj aafshzj 等级： 结帖率：92.86% #10 得分：0 回复于： 2006-10-18 10:38:11 你的理解有一点和我说的不大一样： 2.拿该学生的分数与算出来的每个班级的各科平均分计算差值 我的意思是：将各班各科平均分再求总的各科平均分，然后计算各班各科平均分，哪一个总体和总的各科平均分差值（低于）最大，低的最多的获得下一个学生。 着了你如果要优化也是可以的，即对差值进行加权，如差值最大的一颗给10倍权，差值次大的给5倍权等，然后对所有未分配学生的分数也从新进行加权计算，找出最大的那个。这样效果应该还要好点，但是更复杂。你可以先试试我的第一种，如果基本够用就不要搞这么复杂了，如果不够用可以考虑这种差值加权方法。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 aafshzj aafshzj 等级： 结帖率：92.86% #11 得分：0 回复于： 2006-10-18 10:38:45 着了-〉这里 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 hahahoo hahahoo 等级： 结帖率：97.56% #12 得分：0 回复于： 2006-10-18 10:40:36 问题有些学生会偏科，这样总分低，但是单科高。 光考虑总的涨落会掩盖掉的。 大家再出出主意吧，分大大的有，不够再加，给个千把分的也没有问题。;-) 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 wuhuiITren wuhuiITren 等级： 结帖率：72.97% #13 得分：0 回复于： 2006-10-18 10:43:48 ding 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 aafshzj aafshzj 等级： 结帖率：92.86% #14 得分：0 回复于： 2006-10-18 10:45:19 关键在于偏科的学生不一定都偏同一科啊，总体可能还是随机的。 另外，如果你认为偏科严重影响结果就用我说的几种优化算法。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 fd7893 fd7893 等级： 结帖率：100% #15 得分：0 回复于： 2006-10-18 10:48:52 不要以偏盖全，偏科毕竟是少数，首先要以总平均分作为分班的依据，粗略的分出4个班级，这是第一遍。(偏差肯定是少量的) 后面几遍，再根据单科成绩调整各个班级的个别人！ 要学会简化问题，把问题拆开来就简单的多了。 第一遍分班和后面几遍的算法是不同的，等你完成第一遍分班，再考虑后面的算法！！ 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 hahahoo hahahoo 等级： 结帖率：97.56% #16 得分：0 回复于： 2006-10-18 10:49:01 试试看再说 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 Qim Qim 等级： 结帖率：100% #17 得分：0 回复于： 2006-10-18 10:56:32 估计楼主真是个好老师。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 liangxf0022 liangxf0022 等级： 结帖率：100% #18 得分：0 回复于： 2006-10-18 10:58:06 顶，这个数学上叫多个目标的最优化算法。上网查查，对你有帮助 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 hahahoo hahahoo 等级： 结帖率：97.56% #19 得分：0 回复于： 2006-10-18 11:00:16 惭愧，不是好老师。 现在老师的收益都和绩效挂钩。谁也不愿意带差生班级，所以分班要做到尽量公平，手工做真是一个大工程。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 bjgzxx bjgzxx 等级： 结帖率：100% #20 得分：0 回复于： 2006-10-18 11:48:15 那就用数据库分吧 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 jayskycai jayskycai 等级： 结帖率：90% #21 得分：0 回复于： 2006-10-18 12:18:35 思路： 1：按总分从低到高把学生进行排序 2：按照1,2,3,4 8,7,6,5 9,10,11,12 16,15,14,13 .......... 进行分配。 基本会平衡，且简单可行。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 vosov vosov 等级： 结帖率：100% #22 得分：0 回复于： 2006-10-18 12:53:03 呵呵，同意jayskycai() 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 sunjay117 sunjay117 等级： 结帖率：97.22% #23 得分：0 回复于： 2006-10-18 12:55:04 看看模式设计的一个swimmer里面的算法是不是跟楼主的差不多 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 a2bb a2bb 等级： 结帖率：100% #24 得分：0 回复于： 2006-10-18 13:19:28 性别不管？ 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 a2bb a2bb 等级： 结帖率：100% #25 得分：0 回复于： 2006-10-18 13:19:44 不追求男女搭配？ 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 int64 int64 等级： 结帖率：100% #26 得分：0 回复于： 2006-10-18 13:24:14 坚决要求男女搭配 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 flowersea312 flowersea312 等级： 结帖率：100% #27 得分：0 回复于： 2006-10-18 13:49:45 帮顶了 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 laladeng laladeng 等级： 结帖率：0% #28 得分：0 回复于： 2006-10-18 14:24:07 算法同意jayskycai的方法，一般的分班都是这么分的，第一和第四的差距会被第八和第五弥补（而且这种差距也不大），人数足够多的话，误差基本很小的。至于你说的平均分大致相同，不太可能实现，就是偏科造成的。实际上成绩看的是总分，没必要注重单科平均分，分好的班如果某科好，必定有不好的科，其实很公平，每个个体都有自己的特点，也符合现实逻辑 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 gangzichh gangzichh 等级： 结帖率：100% #29 得分：0 回复于： 2006-10-18 15:52:56 学习ing UP 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 li01bin li01bin 等级： 结帖率：100% #30 得分：30 回复于： 2006-10-18 16:00:03 希望 我来的不算晚。有5年没上csdn了，先跟大家问声好。csdn上面 我最喜欢就是 和大家讨论一些类似的问题了 很有意思。比技术上的东西有意思多了。这个问题 其实是一个经典问题 很多书上都有提到，但我不想从理论上来谈这个问题，因为 我们不是数学家，要想一个 数学上的算法 可能会穷尽我的一生。但有了计算机，我们可以用很人性化的方法 来解决以前看似 根本无法解决的问题，因为 我们虽不是 数学家 但是我们有人类独有的思维方式 最原始的思维方式 归纳跌带。剩下的事 就是让计算机去飞速执行好了。我以前当过一年大学教师，对书本上的理论算法 可以说得上简直是崇拜 总是希望 我的程序可以都向 高斯那样 不用跌代 而直接算出1到100的和一样。从不当老师 到从事了多年实际的开发我发现 那些数学家（其它的家也一样） 是多么值得 社会的尊敬 即使是给再多的money也是不过分的 因为他们是god送给人类 最宝贵的礼物。而且我也完成了从知道自己能做什么 到知道自己不能做什么的一些转变。我的对软件开发的理解 就是choice 和matrix的计算世界的理论 一样。就是看你的选择 没有好坏 因为你是one是不可替代的。现在我来说一下 我的choice: 为了说明方便，我假设共有100名学生，要分2个班。 我们先不管怎么分，但结果肯定是俩个班 而且每个班有50个学生。对吧？ 排列组合：共有100*99/2种组合。 我们可以很容易的用计算机给出我们 这些组合。 下面我们任意取出其中一种，分别算出俩个班中每个班的总分平均，单科平均。 然后用一个校方给定的方式(假设为F)算出俩班的差值S， S=F(A班(总分平均，单科平均)，B班(总分平均，单科平均)) 至于这个F，我们可以自己根据情况来定，比如说总分的权值高，还是单科，其实到这里大家已经看出如何定义F已经不重要了。 最后一定会得到100*99/2个S值，顺利的话，取最小的就好了，然后看看对应最小的那组分发，结果可能连你都大吃一惊，怎么会那么自然和且合理。 归根到底 这次算法 可以算是离散数学里 的一次离散随即的实验而已。 顺便提一下：上面有朋友给出一些算法，是将学生排序什么的。我只想说，校方也没说一定要把好的学生分开,对吧。不分开的话，是可以用中间的一些学生把分数补齐的。 其实 只要改一下F，并且给出一个选择方法，可以保证在分数 差值 最小的基础 可以有多种分法。 例如：分数差值最小，但还是可以给出优略班，但可能会牺牲中间的一部分学生分数来调整了，但话又说回来，中间的这部分学生，还是最稳定的，在哪个班差别不大。哈哈。最让老师头疼的 不是最好的就是最差的，我说对吗？班主？ 最后总结一下这个算法： 易懂 易实现 易扩展 易优化 时间复杂度 C(m,n)`m是人数，n是班数 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 fd7893 fd7893 等级： 结帖率：100% #31 得分：0 回复于： 2006-10-18 16:14:11 强！不出意外LS的应该是正统解法 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 hahahoo hahahoo 等级： 结帖率：97.56% #32 得分：0 回复于： 2006-10-18 16:16:36 按照你的思路，我理解成一个传统的背包问题。 问题是分的班越多，这个排列组合数大的吓人，这样做会不会造成运算时间过长，就难讲了。 如果使用这种算法，我的想法是先按上面所说的，分配掉部分高分的，然后再来迭代，这样会减少点工作量，问题是这个百分比又不好把握。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 hahahoo hahahoo 等级： 结帖率：97.56% #33 得分：0 回复于： 2006-10-18 16:19:26 顺便上传一个刚整理的背包问题的解法，这个版就用C#了 using System; class Fruit { virtual public System.String Name { get { return name; } } virtual public int Price { get { return price; } } virtual public int Size { get { return size; } } private System.String name; private int size; private int price; public Fruit(System.String name, int size, int price) { this.name = name; this.size = size; this.price = price; } } public class Knapsack { [STAThread] public static void Main(System.String[] args) { int MAX = 8; int MIN = 1; int[] item = new int[MAX + 1]; int[] amount = new int[MAX + 1]; Fruit[] fruits = new Fruit[]{ new Fruit("李子", 4, 4500), new Fruit("蘋果", 5, 5700), new Fruit("橘子", 2, 2250), new Fruit("草莓", 1, 1100), new Fruit("甜瓜", 6, 6700)}; for (int i = 0; i < fruits.Length; i++) { for (int s = fruits[i].Size; s <= MAX; s++) { int p = s - fruits[i].Size; int newvalue = amount[p] + fruits[i].Price; if (newvalue > amount[s]) { amount[s] = newvalue; item[s] = i; } } } System.Console.Out.WriteLine("物品\t價格"); for (int i = MAX; i >= MIN; i = i - fruits[item[i]].Size) { System.Console.Out.WriteLine(fruits[item[i]].Name + "\t" + fruits[item[i]].Price); } System.Console.Out.WriteLine("合計\t" + amount[MAX]); } } 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 hahahoo hahahoo 等级： 结帖率：97.56% #34 得分：0 回复于： 2006-10-18 17:57:14 大家继续啊 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 y1g1y1 y1g1y1 等级： 结帖率：100% #35 得分：0 回复于： 2006-10-18 19:26:07 mark 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 li01bin li01bin 等级： 结帖率：100% #36 得分：0 回复于： 2006-10-19 15:05:52 上面我给出的算法是精确的，因为我们打所有的可能都知道了，当然精确了。但haha担心的速度问题是肯定存在的，随着人数和班级的增加，可能连计算机算几千年也算不出来，那么说算法没有意义吗？当然不是，地跪和跌代是有本质差别的，地跪是我们要知道最后算出来的值才可以知道结果，而跌代事每一次算出得值可以作为下次值的查考或修正，其实上面的算法只要加上几个条件就可以了。每一次运算不用算完，只要算几个数就知道这次的分法是不是比上次好，不行直接退出就可以了。 还有其实当人数大到一定程度的时候，最好的方法就是没有方法，闭上眼睛随机分就可以了，我们用计算机模拟过，结果很有现实意义。 概率上看，分数分配符合正态分布，也就是说80%的分数会在一个相对比较集中的区域，你可以画一个曲线图，可以看出所有学生的分数都在平均线上下浮动，你可用比较粗的毛笔延平均线画，用毛笔抹掉的学生是可以不参加计算的。这样10000名学生，估计也就剩下2000名了。 如果是100学生按三门功课分2班，从线性袋鼠看，就是解一个矩阵方程组，求使俩个50*4的矩阵和减平均矩阵的向量长度最短的解。我还没用matlab算过，以后又时间可以看看，估计也快不到哪里，应为本质还是我最开始说的一样，不过作为矩阵计算可能会有些巧妙的方法，maybe。 当然，还可以用计算机模拟，每个班一个班主任，让他们随机轮流选择学生，当然是选者分数最高的那个了，不过没关系，there is banlance we can not see but we can feel it。最后看看结果，或许你会大吃一惊。从概率上看当人数越多，越符合实际情况，人数不多那最好，直接跌归去好了。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 hahahoo hahahoo 等级： 结帖率：97.56% #37 得分：0 回复于： 2006-10-19 17:10:52 因此我现在考虑将各科分数转换成标准分，然后在已标准分的总分进行排序 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 gangzichh gangzichh 等级： 结帖率：100% #38 得分：0 回复于： 2006-10-20 20:21:43 还是觉得这个不错啊 看的也明白些 jayskycai() 思路： 1：按总分从低到高把学生进行排序 2：按照1,2,3,4 8,7,6,5 9,10,11,12 16,15,14,13 .......... 进行分配。 基本会平衡，且简单可行。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 gangzichh gangzichh 等级： 结帖率：100% #39 得分：0 回复于： 2006-10-20 20:22:38 要向hahahoo()学习C#啊 哈哈 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 hahahoo hahahoo 等级： 结帖率：97.56% #40 得分：0 回复于： 2006-10-21 00:10:06 看来没有更好的办法了，本来还想谁弄个什么遗传算法之类的（那东西看不懂），明天晚上前没有什么新的想法的话，就结帖了 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 aafshzj aafshzj 等级： 结帖率：92.86% #41 得分：0 回复于： 2006-10-21 00:42:22 其实基本策略及优化办法都讲过了。 一个最简单的优化就是：（为了提高随机性，你可以把4个班分配一次看成一轮，每一轮开始的班级可以随机产生，滚动进行）。 实际上你可以第一次轮动开始的位置随机产生，以后每一轮开始的位置依次滚动推移。 另外，你不需要将前面百分之多少按固定顺序排，不需要的，都按算法去派就可以了。算法排序不回比固定前面多少位效果差，在非极端情况下，二者结果是一样的，在极端情况下，固定顺序分配反而会有问题。 另外一个优化就是前面提到的差值排序加权办法，稍微复杂点，但通过分别动态分配给多个目标以一个与其离散程度有关的动态权值，能在分配过程中较优地快速收聚各班级的各科平均分。如果需要你也可以采用。但是一般不需要这么复杂了。 我上面提到的基本算法加顺序轮动分配优化，本身已经比实际情况中的分班要细致多了。 对我有用[0] 丢个板砖[0] 引用 | 举报 | 编辑 删除 管理 管理菜单 置顶 推荐 锁定 移动 编辑 删除 帖子加分 帖子高亮 结帖 发帖 回复 写出你眼中的IE11 赢取新年好礼！ 勇敢写出你的爱 赢莫文蔚签名大礼 2014年4月微软MVP申请开始了！ 陈勇- 敏捷开发现状及发展之路 CSDN高校俱乐部 高校全新改版邀你来学习和挑战 本帖子已过去太久远了，不再提供回复功能。 核心技术类目 全部主题 Java VPN Android iOS ERP IE10 Eclipse CRM JavaScript Ubuntu NFC WAP jQuery 数据库 BI HTML5 Spring Apache Hadoop .NET API HTML SDK IIS Fedora XML LBS Unity Splashtop UML components Windows Mobile Rails QEMU KDE Cassandra CloudStack FTC coremail OPhone CouchBase 云计算 iOS6 Rackspace [关闭] [关闭]