上传者: 38687539
|
上传时间: 2022-02-24 23:22:29
|
文件大小: 220KB
|
文件类型: -
程序员面试刷题的书哪个好
具体方案说明相见方案说明书
执行顺序:
./main
./opt
./opt2
./work
根据参数不同,结果会有一定波动,最终大概的效果:
效率:
0.400+,
最好跑到过0.4015+
(远高于冠军队伍的效率值:
0.377)
超时量:
<
1e-3,很多参数下都能跑到0
方差:
一般在0.37左右
main.cpp:
初始解生成
算法流程:按时间顺序遍历每一个任务,用当前空闲人员和任务建立二分图。二分图边权为将该任务分配给某一专家后,会在哪个时间点完成。
用最小费用流算法求二分图最小匹配,按匹配来分配任务
程序中有很多参数都可以调整,如任务的聚集量、人员的聚集量等
opt.cpp,
opt2.cpp:
第一次调优
算法流程:读入第一步中生成的初始解,不断尝试下列调优策略:改派执行任务的专家,交换两个专家的任务
方差公式拆开之后,O(1)时间维护每一项
(具体看代码)
CheckTime函数用于卡时,最终结果取决于时间多少
(以上两步中,均不考虑任务超时问题)
work.cpp:
第二次调优
在这一步中,首先加入空闲专家填补超时的时间
然后不断尝试下列