动态规划独立任务最优调度

---

---

用两台处理机A和B处理n个作业。设第i个作业交给A处理需要时间ai，交给B处理需要时间bi。由于各作业的特点和机器的性能关系，ai和bi之间没有明确的大小关系。既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得这两台机器处理完这n个作业的时间最短。
测试用例：
6（任务数目）
2 5 7 10 5 2（机器A处理这些任务的时间）
3 8 4 11 3 4（机器B处理这些任务的时间）
输出：15

分析：

自己在实际写程序的过程中，写了两种方法。但两种方法思想都大同小异。只不过一个二维数组，一个一维数组。

用二维数组解决：

参考- 独立任务最优调度
先给一个比较容易理解的状态转移方程：
　　用布尔量p(i,j,k)表示前k个任务可由A机在i时间内且B机在j时间内完成。易得：p(i,j,k) = p(i-ak, j, k-1) | p(i, j-bk, k-1).最优结果为p(i,j,n) = true 且 min(max(i, j))。这样表示有两个缺点：一是空间开销大，二是时间花销多。
　　那么， 为什么要先取大再取小呢？？

　　今天上计算机安全学的时候一直在想怎么样把复杂度压缩下来。突破口当然还是i,j下标这个地方，p(i,j,k)表示前k个任务可由A机在i时间内且B机在j时间内完成，如果将其改为int类型，记录的是另一个数组的完成时间，这样就可以降到二维。假设第一维i保留,我们可以用p(i,k)表示前k个任务可由A在i时间内且B在p(i,k)时间内完成。
　　递推方程也容易修改了：第k个任务是由第k-1个任务推出来的，那么第k个任务可由A或B机完成：（第k个任务如果在A上运行，那么A的总的运行时间会增加，但B的时间不变；反之，同理。）
　　如果由A机完成，则有：p(i, k) = p(i - ak, k - 1) (B机时间不变）
　　如果由B机完成，则有：p(i, k) = p(i, k - 1) + bk (A机时间不变）
　　综上分析可得p(i, k) = min( p(i, k – 1) + bk, p(i – ak, k – 1) ). 复杂度为O（n * sigm(ai))。

//用二维数组p表示过程量
#include<stdio.h>
#define n 6         //6个作业
#define MAXTIME 500
int a[n+1]={0,2,5,7,10,5,2};
int b[n+1]={0,3,8,4,11,3,4};
int minTime=10000;
int sa=0;
int p[MAXTIME][n+1]={0};

int main(){
    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;
}

---

用一维数组解决：

思路跟上面的程序相同，只不过p为一位数组，p[i]=j表示所有作业在A上i时间内运行完，在B上j时间内运行完。

//用一位数组p表示过程量
#include<stdio.h>
#include<string.h>
#define n 6         //6个作业
int a[n]={2,5,7,10,5,2};
int b[n]={3,8,4,11,3,4};
int minTime=10000;
int sa=0,sb=0,max=0;

int main(){
    for(int i=0;i<n;i++){
        sa+=a[i];
        sb+=b[i];
    }
    max=sa>sb?sa:sb;

    int p[max+1];
    memset(p,0,sizeof(p));

    for(int k=0;k<n;k++){
        for(int i=max;i>=0;i--){
            p[i]=p[i]+b[k];
            if(i>a[k]){
                p[i]=p[i]<p[i-a[k]]?p[i]:p[i-a[k]];
            }
        }
    }
    
    for(int i=0;i<=max;i++){
        int t=p[i]>i?p[i]:i;
        if(minTime>t)
            minTime=t;
    }
                
    printf("%d\n",minTime);
    return 0;
}

运行截图