一个比较复杂的算法问题求解！！(200分)

Flashcqxg · 2006-11-12

考场安排的算法设计问题
1.有N个学校的学生参加考试,每个学校的考生人数是不定的,取值范围在1-10000之间;
2.将上述学生安排在某个考场参加考试,该考场有M个考室,这M个考室所能容纳的学生不一定都相等,但这M个考室能容纳的学生数肯定大于上述1中的学生总数;
3.要求:
如果一个学校的考生必须安排在几个考室的情况下,则必须排在连续的考室中,不能中间间隔一个其它学校的学生;
如果一个学校的考生能尽量安排在同一个考室的情况下,就不要安排在两个考室中,除非必须拆分;
在同等的条件下,学校的代码(在实际做数据库的时候有一个XXDM来标识学校代码)小的优先考虑;
排过的考室(座位)和学生都不得重复排,即只能排一次;
4.根据上述要求给出最优解,即如果必须拆分组合才能排完考生的情况下,给出最小的拆分组合解来,这个解应该是学校代码和考室的对应.
请给出DELPHI的算法代码，谢谢！

娃娃 · 2006-11-12

SQL:
select xxdm, 学生总数 from 数据表 order xxdm
说明：
memo1为结果显示用
[教室]是保存教室可容纳人数的数组，按教室的号码顺序排序。
i是循环教室
j是当前学校的学生总数
js是保存当前学校所要占用的教室
算法：
i := 0;
j := 0;
js:= '';
memo1.lines.clear;
with 数据集do
begin
j := FieldByName('学生总数').AsInteger;
//进入循环，以该校的考生比当前教室容纳人数少为结束条件
while truedo
begin
js := js + IntToStr(i) + '号 ';
j := j - 教室;
if j >= 0 then

inc(i) //开始下一教室
else
begin
//说明该校学生已经分配完毕，开始下一个学校
memo1.lines.add(FieldByName('XXDM').AsString + '在' + ls + '教室');
js := '';
if Not Eof then
begin
Next;
j := FieldByName('学生总数').AsInteger;
end else
Exit;
//全部学校已经分配完毕
end;

end;
end;

Flashcqxg · 2006-11-13

谢谢二楼的解答，不过此算法好象并不满足我的需求？

tianlove · 2006-11-13

哪里不满足?说来听听,一起讨论

Flashcqxg · 2006-11-13

他的这个算法应该是连续编排下去了。
假设：
一个学校学生有327人，并且也已经连续安排了300人了，都是在前面连续的教室中安排下的，那么假如接下来的教室能安排30个人，那么能安排27人进去，这个教室还有3个位置，这里就可能有好几种情况：
1、某个学校刚刚有3个学生
2、有可能好几个学校只有1人，或有可能好几个学校有两人同时又有好几个学校只有1人
3、上述情况都不存在，其它学校都是超过3个人的的
那么就目前的情况来看，将第1种或第2种情况的学校安排或组合后安排进去，都没有问题；
但总全体安排完成后，还要求有一个最佳的组合来，也就是说，如果组合安排这些教室必须要拆分某个或某几个学校的学生分座在连续的两个教室中的话（应该最多只拆分一次就能容纳完的），那么最终的结果是要求拆分的学校最少即要求的最优解。

wp231957 · 2006-11-13

好难

Flashcqxg · 2006-11-13

确实比较难
主要是我的数学没有学好，不然的话，应该能够找一个比较接近的数学模型来解决。

网中戏 · 2006-11-14

Flashcqxg · 2006-11-15

谢谢帮顶

一个比较复杂的算法问题求解！！(200分)

Flashcqxg

Unregistered / Unconfirmed

娃娃

Unregistered / Unconfirmed

Flashcqxg

Unregistered / Unconfirmed

tianlove

Unregistered / Unconfirmed

Flashcqxg

Unregistered / Unconfirmed

wp231957

Unregistered / Unconfirmed

Flashcqxg

Unregistered / Unconfirmed

网中戏

Unregistered / Unconfirmed

Flashcqxg

Unregistered / Unconfirmed

Similar threads