算法实现题 5-15 最佳调度问题

问题描述：假设有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。试设计一个算法找出完成这n个任务的最佳调度，使得完成全部任务的时间最早。

算法设计：对任意给定的整数n和k，以及完成任务i需要的时间为ti，i=1~n。编程计算完成这n个任务的最佳调度。

输入：给出输入数据。第一行有2 个正整数n和k。第2 行的n个正整数是完成n个任务需要的时间。

输出：将计算出的完成全部任务的最早时间输出

输入
7  3
2  14  4  16  6  5  3
输出
17

按照书上解答书给的函数写的。做了一点点的更改。

 

#include <bits/stdc++.h>
using namespace std;

int n,k;
int a[999];
int len[999];//记录当前晚上前i个任务需要的时间 
int best=999;//记录最小的时间 

void backtrack(int dep) {
	if(dep==n) {
		int tmp=0;
		for(int i=0; i<k; i++) {
			if(len[i]>tmp)
				tmp=len[i];//找出k个机器中时间最长的 
		}
		if(tmp<best)//如果时间小于之前的best，更新数据 
			best=tmp;
		return ;
	}
	for(int i=0; i<k; i++) {
		len[i]=len[i]+a[dep];
		if(len[i]<best)
			backtrack(dep+1);
		len[i]=len[i]-a[dep];//回溯 
	}
}

int main() {
	cin>>n>>k;
	for(int i=0; i<n; i++)
		cin>>a[i];
	backtrack(0);
	cout<<best<<endl;
	return 0;
}
/*
输入
7 3
2 14 4 16 6 5 3
输出
17
*/