算法实现——独立任务最优调度问题（C实现）

╰半橙微兮° 2024-03-24 15:23 15阅读 0赞

**问题描述**：用两台处理机A、B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各个作业的特点和机器性能的关系，很可能对于某些i，有![a\_\{i\}\\geq b\_\{i\}][a_i_geq b_i]，而对于某些 j ，![j\\neq i][j_neq i]，有![a\_\{i\}< b\_\{i\}][a_i_ b_i]。既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得2台机器处理完这n个作业的最短时间（从任意一台机器开工到最后一台机器停工的总时间）。研究一个实例：![(a\_\{1\},a\_\{2\},a\_\{3\},a\_\{4\},a\_\{5\},a\_\{6\})=(2,5,7,10,5,2)][a_1_a_2_a_3_a_4_a_5_a_6_2_5_7_10_5_2],![(b\_\{1\},b\_\{2\},b\_\{3\},b\_\{4\},b\_\{5\},b\_\{6\})=(3,8,4,11,3,4)][b_1_b_2_b_3_b_4_b_5_b_6_3_8_4_11_3_4]。

**算法分析：**对于2台给定的处理机A和B处理个作业，找出一个最优调度方案，使2台机器处理外这n个作业的时间最短。

**输入数据：**由文件input.txt提供输入数据。文件的第一行是1个正整数n，表示要处理的n个作业。在接下来的两行中，每行有n个正整数，分别代表处理机A和B处理第i个作业需要的处理时间。

**结果输出**：将计算出的最短处理时间输出到文件output.txt。

#include<stdio.h>
    #define MAXTIME 500
    int a[MAXTIME];
    int b[MAXTIME];
    int minTime=10000;
    int sa=0;//所有作业在机器A上运行是所需要的时间 
    
    int main(){
    	int n;//n个作业 
    	
    	freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        
        scanf("%d",&n);        //读入作业个数 
          
        for(int i=1;i<n+1;i++)//读入机器A运行时间 
        scanf("%d",&a[i]);
        for(int i=1;i<n+1;i++)//读入机器B运行时间 
        scanf("%d",&b[i]);
        
        int p[MAXTIME][n+1]={0};
        
        for(int k=1;k<=n;k++) //代表作业
    	{ 
            sa+=a[k];       //假设都在A上运行，得出时间和sa
    
            for(int i=0;i<=sa;i++)
            {
                p[i][k]=p[i][k-1]+b[k];
                if(i>=a[k]){             //当前时间是否满足其在机器a上运行
                    p[i][k]=p[i][k]<p[i-a[k]][k-1]?p[i][k]:p[i-a[k]][k-1];
                }
            }
        }
        
        for(int i=0;i<=sa;i++){         //遍历p数组，p[i][n]的值是n个作
            int t=(p[i][n]>i?p[i][n]:i);//业在B上运行时间，i意思是n个作业在A上运行时间
            if(minTime>t)               
                minTime=t;
        }
                    
        printf("%d\n",minTime);
        return 0;
    }

那么现在来检验一下吧~

(1)在代码相同路径下建立题目所需要的文件

![9ac87e0370b1424bb978445ad762964f.png][]

（2）在input.txt文件中输入所需要检验的例题

![560f78ea9983432a96ee5101a5a3d4ff.png][]

（3）运行代码

![e20db7a6567040d0882fa5b6bb9ca0ea.png][]

（4）打开output.txt文件进行检验

![6087a0113d9b458cb1671045f3dcf97f.png][]

检验完毕~

当然还有多种方法，本文章只使用了其中的一种，相信小伙伴们可以探索出更简单、更合理的程序的~

[a_i_geq b_i]: https://latex.csdn.net/eq?a_%7Bi%7D%5Cgeq%20b_%7Bi%7D
[j_neq i]: https://latex.csdn.net/eq?j%5Cneq%20i
[a_i_ b_i]: https://latex.csdn.net/eq?a_%7Bi%7D%3C%20b_%7Bi%7D
[a_1_a_2_a_3_a_4_a_5_a_6_2_5_7_10_5_2]: https://latex.csdn.net/eq?%28a_%7B1%7D%2Ca_%7B2%7D%2Ca_%7B3%7D%2Ca_%7B4%7D%2Ca_%7B5%7D%2Ca_%7B6%7D%29%3D%282%2C5%2C7%2C10%2C5%2C2%29
[b_1_b_2_b_3_b_4_b_5_b_6_3_8_4_11_3_4]: https://latex.csdn.net/eq?%28b_%7B1%7D%2Cb_%7B2%7D%2Cb_%7B3%7D%2Cb_%7B4%7D%2Cb_%7B5%7D%2Cb_%7B6%7D%29%3D%283%2C8%2C4%2C11%2C3%2C4%29
[9ac87e0370b1424bb978445ad762964f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/4fa26186028d4055a3ee2042db71176b.png
[560f78ea9983432a96ee5101a5a3d4ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/6391c093347e4ea79ee050a18e4c09c7.png
[e20db7a6567040d0882fa5b6bb9ca0ea.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/110f973037d14b71833aafabfea3aeb9.png
[6087a0113d9b458cb1671045f3dcf97f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/7f1a45270fec4f349fa62cb692ffbc3a.png