独立任务最优调度问题

这是一道动态规划问题，提到它的原因是，我个人觉得解法挺有趣的，可能是因为见识少，没遇到过这样解决问题的。

问题

【问题描述】用两台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai, 若由机器B处理，则需要时间bi 。由于各作业的特点和机器的性能关系，可能对于某些i，有ai>=bi，而对于某些j(j!=i，j不等于i)，有aj<bj。即不能将一个作业分开由两台机器处理，也没有一台机器能同时处理2个作业。设计一个动态规划算法，使得这两台机器处理完成这n个作业的时间最短（从任何一台机器开工到最后一台机器停工的总时间）。

研究一个实例：(a1, a2, a3, a4, a5, a6)=(2, 5, 7, 10, 5, 2), (b1, b2, b3, b4, b5, b6, )=(3, 8, 4, 11, 3, 4) 【算法设计】对于给定的两台处理机A和B处理n个作业，找出一个最优调度方案，使2台机器处理完成这n个作业的时间最短。（每个数之间用空格隔开）

【输入形式】第一行是1个正整数n，表示要处理n个作业。在接下来的2行中，每行有n个正整数，分别表示处理机A和B处理第i个作业需要的处理时间。

【输出形式】将最短处理时间输出。

【样例输入】

6
2 5 7 10 5 2
3 8 4 11 3 4

【样例输出】

15

题解

利用dp存储每个状态的结果，最后选出最优的一个解。转换方程：dp[i][j]=min(dp[i-1][j]+b[i],dp[i-1][j-a[i]]);dp[i][j]代表做完前i个任务，A机器花几分钟情况下，B机器所花的时间，也就是说dp[i][j]就是表示B机器所花时间。

dp[i][j] = dp[i-1][j]+b[i]代表第i个任务交给B来做，所以做完前i个任务的时候,A机器和前i - 1的任务一样，还是花了j分钟，而B机器则花dp[i-1][j]+b[i]分钟；

dp[i][j] = dp[i-1][j-a[i]]代表第i个任务交给A来做，现在的A机器花费时间是j，所以在前i - 1个任务完成的时候，A机器是花了j-a[i]分钟的，所以现在B机器还是花了dp[i-1][j-a[i]]分钟；

一直到dp[n][i]:代表所有的任务都做完了，B机器所花费的时间，那么最迟的时间就是B的时间和A的时间求最大值；

for(int i=0; i<=sum; i++)ans=min(ans,max(dp[n][i],i));//max(dp[n][i],i) 表示完成前n个作业A机器花i分钟 B机器花dp[n][i]分钟情况下，最迟完工时间。

#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
int a[201], b[201];
int n;
int dp[202][10000];//dp[i][j] 表示前i个作业中A机器花j分钟的时候 B机器所花时间 
int main(int argc, char* argv[]) {
    cin >> n;
    memset(dp,0,sizeof(dp));
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++) cin>>b[i];
    int sum=0;
    for(int i=1; i<=n; i++) {
        sum+=a[i];
        for(int j=0; j<=sum; j++) {
            dp[i][j]=dp[i-1][j]+b[i];
            if(j>=a[i]) dp[i][j]=min(dp[i-1][j]+b[i],dp[i-1][j-a[i]]);
        }
    }
    int ans=999999;
    //max(dp[n][i],i) 表示完成前n个作业A机器花i分钟 B机器花dp[n][i]分钟情况下，最迟完工时间 
    for(int i=0; i<=sum; i++)ans=min(ans,max(dp[n][i],i));
    cout<<ans<<endl;
    return 0;
}

可能有些人并没有觉得这个解有什么特殊的，但认真看这个dp数组会发现它是挺有意思的，重复上面的dp[i][j]代表做完前i个任务，A机器花几分钟情况下，B机器所花的时间，也就是说dp[i][j]就是表示B机器所花时间，而同时又显示了A机器花的时间。这样一来就可用二维数组表示B机器和A机器所花的时间了，查看我的教材答案用的却是三维数组，明显更麻烦一些，对这个的话只需最后再找到最长时间便可，也不至于三维数组。

也就我这种见识少的会感叹这种解法，大牛们应该也瞧不上这，仍需要做题啊。

参考

独立任务最优调度问题

其实几乎就是搬运，再加上自己看法