最佳调度（回溯法）

最佳调度问题 【问题描述】 假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间最早。 【编程任务】 对任意给定的整数n和k，以及完成任务i需要的时间为ti，i=1~n。编程计算完成这n个任务的最佳调度。 【输入样例】 7 3 2 14 4 16 6 5 3 【输出样例】 17

首先列个七乘三的二维数组了解算法思路：

我们知道回溯法其实是穷举法加剪枝函数

我们的函数用到递归，层层返回。

解空间树为一颗n叉树，每搜索到叶子节点就更新一次最大值，是用一次搜索结束后三个机器中花费时间最长的机器的所用时间作为此次分配的所用时间。 上图：红色为第一次分配；黄背景色为第二次；加粗字体为第三次；下划线为第四次。从上到下递归，然后层层返回。

算法设计： 从n个作业中找出有最小完成时间和的作业调度，所以批处理作业调度问题的解空间是一棵排列树。按照回溯法搜索排列树的算法框架，设开始时t=[1,2, … , n]是所给的n个作业的完成时间，则相应的排列树由t[1:n]的所有排列构成。 数组len[]用于存储一组空间解，comp()函数用于计算一个完整调度的完成时间，search()函数用来做搜索，best记录相应的当前最佳作业调度完成时间。 当dep>n时，算法搜索至叶子结点，得到一个新的作业调度方案。此时算法适时更新当前最优值和相应的当前最佳调度。 当dep if(dep==n) { int tmp=comp(); if(tmp int i,time[99];

/读文件 input，将结果保存到all数组 FILE *fpRead=fopen(“input.txt”,“r”); if(fpRead==NULL) { return 0; } for(i=0;i if(all[i]!=0) time[i-2]=all[i]; best=all[i]+best; } for (i=0; i