算法与分析课程_回溯算法_拼题网_习题1_最佳调度问题_C++

1 最佳调度问题
假设有n（n<=20）个任务由k（k<=20）个可并行工作的机器完成。完成任务i需要的时间为ti。 试设计一个算法，对任意给定的整数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
#include
#include
#include
using namespace std;
class Solution {
public:void backTrace(int pidLabel, vector<int>& pidInfo, vector<int> &machineInfo,int &minTime) {if (pidLabel==pidInfo.size()) {//全部任务已经执行int nowTime = 0;for (int i = 0; i < machineInfo.size(); i++) {//找出当前方案所需时间最大值nowTime = max(nowTime, machineInfo.at(i));}minTime = min(minTime, nowTime);//找出完成所有进程的最小时间}else {for (int i = 0; i < machineInfo.size(); i++) {machineInfo.at(i) += pidInfo.at(pidLabel);//i号机器完成pidLabel号任务if (machineInfo.at(i) < minTime) {//如果当前机器完成任务的时间大于别的方案全部完成时间的最小值backTrace(pidLabel+1, pidInfo,machineInfo,minTime);}machineInfo.at(i) -= pidInfo.at(pidLabel);}}}
};
int main() {int n, k;cin >> n >> k;int minTime = 0;vector<int> pidInfo(n,0);vector<int> machineInfo(k,0);for (int i = 0; i < n; i++) {cin >> pidInfo.at(i);minTime+= pidInfo.at(i);}Solution A;A.backTrace(0,pidInfo,machineInfo,minTime);cout << minTime << endl;system("pause");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！