最佳调度问题_分⽀限界法
最佳调度问题
【问题描述】天空游戏宝典
假设有n个任务由k个可并⾏⼯作的机器完成。完成任务i需要的时间为ti。试设计⼀个算法出完成这n个任务的最佳调度，使得完成全部任务的时间最早。 【编程任务】
对任意给定的整数n和k，以及完成任务i需要的时间为ti，i=1~n。编程计算完成这n个任务的最佳调度。
【输⼊样例】
7 3
2 14 4 16 6 5 3
【输出样例】
17
即此问题为七个任务，三台机器。
⾸先列个七乘三的⼆维数组了解算法思路：
静穆我们知道回溯法其实是穷举法加剪枝函数，我们的函数⽤到递归，层层返回。⼀共七层，每层的除去叶⼦节点都有三个孩⼦
每搜索到叶⼦节点就更新⼀次maxnum值（⼩于maxnum则更新）（初值为⼀个较⼤的数），是⽤⼀次搜索结束后三个机器中花费时间最长的机器的所⽤时间作为此次分配的所⽤时间，。
胃内容物
1 #include<bits/stdc++.h>
2using namespace std;
3int n,k;
4int x[100];//机器
5int x1[100];//作业
逆行性遗忘
6int maxnum=1000000;
7
8void task(int level)
9 {
10if(level>n){
11int temp=0;
12for(int i=1;i<=k;i++){
13if(x[i]>temp){
14 temp=x[i];
15 }
16 }
17if(temp<maxnum){
18 maxnum=temp;
19 }
20 }
21else{
22for(int i=1;i<=k;i++){
23 x[i]+=x1[level];
24 task(level+1);
25 x[i]-=x1[level];
26 }
27 }
牧一征28 }
29int main()
30 {
31 cin >> n;
32 cin >> k;
33for(int i=1;i<=n;i++){
34 cin >>x1[i];
35 }
36 task(1);
37 cout << maxnum;
38return0;佳木斯工学院
39 }
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议