独立任务最优调度（动态规划）
题目：
用两台处理机 A 和 B 处理 n 个作业。设 A 和 B 处理第 k 个作业的时间分别为 ak 和 bk 。由于各个作业的特点和机器性能的关系，对某些作业，在 A 上的处理时间长；而对另一些作业，在 B 上的处理时间更长。一台处理机在某个时刻只能处理一个作业，而且作业处理是不可中断的，每个作业只能被处理一次。现在要找出一个最优调度方案，使得 n 个作业被这两台处理机处理完毕的时间和最少。
算法思路：
当完成 k 个作业时，设机器 A 花费了 x 时间，机器 B 花费时间的最小值肯定是 x 的一个函数。设 F[k,x] 表示完成k个作业且机器 A 花费 x 时间的条件下机器 B 所花费时间的最小值，那么 F[k,x]=min{F[k?1,x]+bk,F[k?1,x?ak]} 。其中 F[k?1,x]+bk 表示第k个作业由机器B来处理，完成前 k?1 个作业时机器 A 所花费的时间还是 x 。而 F[k?1,x?ak] 表示第 k 个作业由机器 A 来处理，此时完成前 k?1 个作业机器A花费的时间是 x?ak 。
????根据 F 的定义，我们知道 F[n,x] 表示完成 n 个作业且机器 A 花费 x 时间的条件下机器 B 所花费时间的最小值。显然， 0≤x≤∑k=0nak ，所以对于 xi( 区间 [0,∑k=0nak] 内的任一整数 ) ，总有一个 F[n,xi] 与其对应，那么 min{max{xi,F[n,xi]}} 就是最后的结果。由于要处理每个作业 k ，并且处理每个作业 k 的时候都要循环 ∑j=0kaj 次，所以算法的时间复杂度为 O(n∑k=0nak) 。
????考虑以下包含 6 个作业的例子，其中 ak={2,5,7,10,5,2} ，而 bk={3,8,4,11,3,4} 。下面对前两个作业进行简单的分析。
【独立任务最优调度（动态规划）】
| 作业1 | 作业2 | 作业3 | 作业4 | 作业5 | 作业6 | |
| 处理机A | 2 | 5 | 7 | 10 | 5 | 2 |
| 处理机B | 3 | 8 | 4 | 11 | 3 | 4 |
（2）对于第二个作业， x 的取值范围是 0≤x≤a1+a2 。当 x<0 时，同样设 F[2,x]=∞ 。
（3）下面是详细步骤：
x=0 ，F[2,0]=min{F[1,0]+b2,F[1,0?a2]}=min{3+8,∞}=11 ，所以 max(0,11)=11 ；
???? x=1 ， F[2,1]=min{F[1,1]+b2,F[1,1?a2]}=min{3+8,∞}=11 ，所以 max(1,11)=11 ；
???? x=2 ， F[2,2]=min{F[1,2]+b2,F[1,2?a2]}=min{0+8,∞}=8 ，所以 max(2,8)=8 ；
???? x=3 ， F[2,3]=min{F[1,3]+b2,F[1,3?a2]}=min{0+8,∞}=8 ，所以 max(3,8)=8 ；
???? x=4 ， F[2,4]=min{F[1,4]+b2,F[1,4?a2]}=min{0+8,∞}=8 ，所以 max(4,8)=8 ；
???? x=5 ， F[2,5]=min{F[1,5]+b2,F[1,5?a2]}=min{0+8,3}=3 ，所以 max(5,3)=5 ；
???? x=6 ， F[2,6]=min{F[1,6]+b2,F[1,6?a2]}=min{0+8,3}=3 ，所以 max(6,3)=6 ；
???? x=7 ， F[2,7]=min{F[1,7]+b2,F[1,7?a2]}=min{0+8,0}=0 ，所以 max(7,0)=7 ；
依次类推
下面是代码的实现：
#includeusing namespace std;
void Read(int *a,int *b,int n)///输入对应的时间值{cout<<"请输入机器A处理每个作业的时间：";
for(int i=1;
i<=n;
i++){cin>>a[i];
}cout<>b[i];
}}int min(int x, int y){return x < y ? x : y;
}int max(int x, int y){return x > y ? x : y;
}int dyna(int *a,int *b,int **F,int n,int *time){int sumA=a[1];
///一开始的时间///当k=1的时候for(int x=0;
x>n;
int *a=new int[n];
int *b=new int[n];
int **F=new int *[n];
int *time=new int[n];
for(int i=1;
i<=n;
i++){F[i]=new int[n*n];
}Read(a,b,n);
cout< 下面是运行结果如下：
文章图片
推荐阅读
- 五年后，我要成为独立自强自信的女性
- 多线程NSOperation
- 热闹也可以，独立也可以，随时有选择的权利
- 尊重和独立，坦然面对婚姻
- linux定时任务contab
- 242为什么不断切换任务会更容易累（）
- IOST任务教程
- 时间管理的任务模型
- 随便写写，完成任务?
- 体学文化，体学观，可以通观世界万物的渊源。我是在高人的督促下，走出一条独立的人类本体学研究和发展新路来了