一、问题如下：
问题描述：
假设有 n 个任务由 k 个可并行工作的机器来完成。完成任务 i 需要时间为ti ，设计完成这 n 个任务的最佳调度算法，使得完成全部任务的时间最早。
编程任务：
对任意给定的整数n和k，以及完成任务i需要的时间为ti，i=1,2,…,n。编程计算完成这n个任务的最佳调度。
输入样例：
(第一行为任务数n，第二行为可并行工作的机器数k，第三行为机器完成任务i所需的单位时间)
10
7
67 45 80 32 59 95 37 46 28 20
输出样例：（第一行是完成所有任务的最优化时间）
95
二、回溯剪枝关键步骤
剪枝关键步骤一/代码中第15行：
if(y>MaxNum) return; //大于最大时间上限，放弃此调度安排；
剪枝关键步骤二/代码第21段：
if(time[x]+MachineTime[i]<=MaxNum) 仍然是放弃大于MaxNum的调度安排。
三、代码如下：
#include <iostream> #include <algorithm>//max()函数头文件 using namespace std; #define N 1000 //求最优化问题，即最小调度 int MaxNum=100000; int n;//任务数 int k;//机器数 int time[N];//存放任务时间 int MachineTime[N]={0};//存放机器的运行时间 void DFS(int x,int y){//x为已放入机器的任务数,y为目前耗费的最大时间 if(y>MaxNum) return;//大于最大时间上限，放弃此调度安排；(剪枝关键步骤1) if(x==n){//n个任务皆放入机器执行完毕 if(y<MaxNum) MaxNum=y; //(更新需要的最大调度时间MaxNum) return; } for(int i=1;i<=k;i++){//对k台机器遍历 if(time[x]+MachineTime[i]<=MaxNum){//(剪枝关键步骤二) MachineTime[i]=MachineTime[i]+time[x];//把任务x放入机器i执行 DFS(x+1,max(y,MachineTime[i]));//递归调用 MachineTime[i]=MachineTime[i]-time[x];//回溯 } } return; } int main(){ cin>>n>>k; for(int i=0;i<n;i++){//输入任务时间 cin>>time[i]; } DFS(0,0);//调用 cout<<MaxNum<<endl;//输出 return 0; }
