请高手指教——按要求分班

灰袍法师

ex121 发表于 2012-7-25 15:07
法师的基本思路是怎样的啊?
能介绍一下吗?
谢谢!

简单注释一下关键代码，基本的算法就是二楼 DataBus 说的随机分
不过具体做法是：前50%的学生随机分配，这样会导致每班学生人数不一样
所以后50%的学生直接分配到人数最少的班
重要的是对分配方案的评估函数，这里用的是所有科目的分差的平方和最低
For k = 1 To loop_times

清空每个物品分配到哪个容器的记录 plan(1 to item_count)
清空每个容器的人数记录 plan_rec(1 to item_count)

ReDim plan(1 To item_count)
ReDim pack_rec(1 To pack_count)

For i = 1 To item_count

        对于所有的待分配物品，如果属于前50%，随机分配到某个容器
    If i <= 0.5 * item_count Then
        pos = Int(Rnd * pack_count) + 1

        对于所有的待分配物品，如果属于后50%，分配到人数最少的那个容器，以保持每个班人数平衡
    Else
        min_pack = pack_rec(1)
        pos = 1
        For j = 2 To pack_count
            If pack_rec(j) < min_pack Then
                min_pack = pack_rec(j)
                pos = j
            End If
        Next j
    End If

    分配方案的第i个人，分配到第 pos 个班，该班的人数记录＋1
    plan(i) = pos
    pack_rec(pos) = pack_rec(pos) + 1
Next i

这里是最关键的部分，对分配好的方案 plan()，进行评估，给出一个分数
Call Evaluate(plan, result)

如果分数比之前的分配方案更好，就保留。
If result < best_result Then
    best_result = result
    best_plan = plan
End If
Next k

评估函数
Sub Evaluate(plan() As Long, result)
Dim p As Long, q As Long, pos As Long, key As Long
Dim count(), avg(), total()

记录每个科目的总分，平均分，人数的数组
ReDim total(1 To pack_count, 1 To key_count)
ReDim avg(1 To pack_count, 1 To key_count)
ReDim count(1 To pack_count)

计算总分和人数
For p = 1 To item_count
    pos = plan(p)
    count(pos) = count(pos) + 1
    For q = 1 To key_count
        total(pos, q) = total(pos, q) + data(p, q)
    Next q
Next p

计算平均分
For p = 1 To pack_count
    For q = 1 To key_count
        avg(p, q) = total(p, q) / count(p)
    Next q
Next p

求出每个科目的班最低平均分，最高平均分
ReDim max_avg(1 To key_count)
ReDim min_avg(1 To key_count)
For p = 1 To key_count
    max_avg(p) = avg(1, p)
    min_avg(p) = avg(1, p)
Next p

For p = 1 To key_count
    For q = 2 To pack_count
        If avg(q, p) > max_avg(p) Then max_avg(p) = avg(q, p)
        If avg(q, p) < min_avg(p) Then min_avg(p) = avg(q, p)
    Next q
Next p

打分了。。。
这里的评判标准很简单，每个科目的最高平均分 - 最低平均分，取平方和
然后把每个科目的这个平方和结果加起来
作为分配方案的最终分数（即要求每个科目的分差越低越好）
你可以给出各种不同的评估标准
如要求 总分的分差越低越好，就可以给总分的分差平方和乘以一个权重，如 x10
这样得到的最佳分班，将会有个比较低的总分分差，但是某一单科分差可能会比较高

result = 0
For p = 1 To key_count
    result = result + (max_avg(p) - min_avg(p)) ^ 2
Next p
这里补一句给最后一项科目的分差的平方和，多10倍的权重，求出的总分平均分结果更好！
    result = result + 10 * (max_avg(key_count) - min_avg(key_count)) ^ 2

End Sub

ex121

灰袍法师 发表于 2012-7-25 16:13
简单注释一下关键代码，基本的算法就是二楼 DataBus 说的随机分
不过具体做法是：前50%的学生随机分配， ...

法师真乃神人也.
我再修行几辈子也望尘莫及呵.

yanziyang223

excelw 发表于 2012-7-24 07:56

我给你做的那个分班难道不好用吗，貌似每个班分的成绩都是差不多的呢，就是要收工把男、女生分成两个表而已，剩下的六个人男女不能平均分配了，只能人工调整了，这个分班到最后都得这样，你不要想一个公式能解决你的问题，那样是很难实现的，除非男、女生人数刚刚好能分6个班

灰袍法师

17楼补充了一个分批次分班的方法，可以解决随机算法求解精度不高的毛病
方法是缩减每次分班的规模，从而得到更高的精度和求解速度。
当然，对于极大数量的学生和班级数，这个方法也是不中用的
如分5000学生到100个班。。。。。。

aoe1981

灰袍法师 发表于 2012-7-24 19:51
附件是最无脑的随机分班法，设定更多的随机次数可以获得更好的结果
学生数班数越多，效果越差；学生数班数 ...

多次分班，好！思路愈加宽广了……

hasyh2008

学习！！！！！！！