有没有八字大神看一下下这个bug

来源：蜘蛛抓取(WebSpider) 时间：2018-12-03 12:08 标签： 八字大神看一下

11089 多机最佳调度（优先做）
提交次數:0 通过次数:0

假设有n个任务（n<=100）m台机器（m<=50），任务可以由任何一个机器完成但不可以拆分任务或执行过程中中途停下，
第i个任务完成需偠的时间为ti

请设计两种算法（一种采用贪心算法，另一种采用回溯算法）找出完成这n个任务的最佳调度，使得最早时间完成全部任务

这里采用两种算法来求解：
1）贪心算法可以得到近似的最早完成时间，算法思想在书上4.7节
2）回溯算法搜索m叉树（除叶节点外每个节点m個儿子），寻找最早的完成时间

输入两行，第一行为n和m中间空格相连（其中n表示任务的数量，m表示机器的数量）（n<=100, m<=50）。
第二行的n个數是任务i的处理时间ti

输出两行，第一行为采用贪心算法算出的最早完成时间第二行为采用回溯算法搜索出的最早完成时间。

第（1）个貪心算法按书上思想去实现：总将更长的作业分给最早空闲的机器

第（2）个就是在m叉树上深度优先搜寻最优解的过程。
//t数组为初始的任務处理时间；
//len2是个数组：m个元素对应m台机的空闲时间即第二种回溯算法在搜索过程中已探察过任务且针对某台机的完成时间和；
//x数组用來保存探察过的任务编号。
…… //这个省略号要你自己来扩展了，要找到最好的叶子（即最早完成时间的一组最优调度）

int* x;//每个任务使用的機器编号

我要回帖

更多关于 八字大神看一下 的文章

 

随机推荐