算法设计实验报告
题 目： 独立任务最优调度问题
年 月 日
一、实验题目
独立任务最优调度问题
二、实验目的
问题描述：用2 台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间????，若由机器B来处理，则需要时间???? 。由于各作业的特点和机器的性能关系，很可能对于某些i，有????=>????，而对于某些 j，j≠i，有????
三、实验内容
算法设计：对于给定的两台处理机A和B处理n个作业，找出一个最优调度方案使两台机器处理完这n个作业的时间最短。
数据输入：由文件input.txt提供输入数据。文件的第一行是一个正整数n，表示要处理n个作业。在接下来的2行中，每行n个正整数，分别表示处理机A和B处理第 个作业需要的处理时间。
结果输出:将计算出的最短处理时间输出到文件output.txt。 输入文件示例 输出文件示例 input.txt output.txt 6 15 2 5 7 10 5 2 3 8 4 11 3 4
四、实验原理
首先要注意每个作业仅需要处理一次就行，不需要被机器A和B各处理一遍
采用动态规划;定义t[i][j]为：表示完成i个作业且机器A花费j时间的条件下机器B所花费时间的最小值，那么t[i][j] = min{t[i-1][j] + b[i], t[i-1][j-a[i]]}。
假设前i-1件已经被处理了，那么第 i 件作业由谁来处理可以分两种情况：
1）由机器A处理i，则机器B的时间为 t[i-1][j-a[i]]; 2）由机器B处理i，则机器B的时间为 t[i-1][j]+b[i];
3）特殊情况，如果j < a[i],则不可能由机器A来完成，此时t[i][j] = t[i-1][j]+b[i]；
最终t[i][j] 选择1）和2）中较小的一个，即t[i][j] = min{t[i- 1][j]+b[i], t[i-1][j-a[i]]}。
五、实验步骤
1）实验环境：Microsoft Visual Studio 2010
2）编写代码，在程序文件夹下建立input.txt，output.txt，输入题目，不断调试运行。
3）实验代码
#include
int main() {
int i,j,n; int sum=0;
int a[N]={0},b[N]={0},t[N][N]={0};
freopen(\,\,stdin); freopen(\,\,stdout);
scanf(\,&n); for(i=0;i for(j=0;j for(i=1;i<=n;i++) { for(j=0;j<=sum;j++) { if(j else if(t[i-1][j-a[i-1]]>t[i-1][j]+b[i-1]) t[i][j]=t[i-1][j]+b[i-1]; else t[i][j]=t[i-1][j-a[i-1]]; } } int min=1000000; for(i=0;i<=sum;i++) { j=t[n][i]>i?t[n][i]:i; if(min>j) { min=j; } } printf(\,min); return 0; } 六、实验结果分析 本次实验采用动态规划法完成，由于两机器可以同时工作，A的运行对B的运行没有影响，确定了第i件任务由谁来完成，B花的时间最短，然后再从A和B中取得最晚的停机时间，就可以确定A和B完成任务的最短时间。所以问题满足最优子结构性质。 算法复杂度：由于对于每个任务，需要遍历A所花的所有时间，设任务有n 个，A花费时间总和为m，计算t[i][j]花费的时间为常数级别，所以时间复杂度为O(nm),空间复杂度就是一个二维数组nm。 运行结果如下：
算法分析与设计-独立任务最优调度问题实验报告
