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

问题描述

给出了每个作业在A、B处理机上处理的时间，我们应该找出所有任务全部完成的调度时间。

题目分析

题目要求我们设计一个动态规划算法，计算出完成所有作业所用的最短时间。
根据我们动态规划的基本框架，先找到状态，然后选择，最终写出状态转移方程。
那我们先看一下状态，这里面的状态无非是作业处理时间以及哪个机器来处理作业。所以我们只需要对这几个状态来进行选择。然后写出状态转移方程即可。
这道题的状态转移方程有点难想，但是如果从选择的角度就没那么困难。
我们应该选择什么呢？这里面无非只有两个机器，所以我们只需要对机器进行选择即可，即当前工作应该选择哪个机器来执行。
我们的目的是选择最短的运行时间，所以我们的状态转移方程需要体现时间量。下面我们给出状态转移方程：F[i][j] = min(F[i-1][j-a[i]],F[i-1][j]+b[i])。
F[i][j]表示第i个工作，A机器花费的时间为j的情况下,B机器处理的最短时间。
从这个状态转移方程我们可以看出来,当i-1个作业被处理完了，该选择谁来处理第i个作业呢？
F[i-1][j]+b[i]表示第i个作业A机器不去做，交给B机器做，B处理的时间；而F[i-1][j-a[i]表示作业i由机器A处理，B不需要管，所以B机器处理的时间就是上一个作业的处理时间，即为F[i-1][j-a[i]]。
明确了状态转移函数，我们再来明确一下我们的目标，我们的目的是找到最短时间没错，但是完成任务最短时间由什么决定呢？应该由A机器完成时间和B机器完成时间中最大的那一个决定。因为一项任务真正的完工需要等待两个同时完工才算完成。
所以我们可以明确了，在确定B机器处理时间时，我们会取最小值；当计算作业完成时间时，我们要取A、B中的最大值，最后还要取最小值才表示完成作业的最短时间(这里取的最小值是分配问题，即作业由A机器处理的时间会产生不同，我们先算出A处理所用的总时间，在这个时间范围内进行遍历，所有分配种类中取最小。)

#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]]);
        }
    }
    //max(dp[n][i],i) 表示完成前n个作业A机器花i分钟 B机器花dp[n][i]分钟情况下，最迟完工时间 
 int ans=999999;
    for(int i=0; i<=sum; i++)ans=min(ans,max(dp[n][i],i));
    cout<<ans<<endl;
    return 0;
} 

总结

算法的时间复杂度取决于机器A处理的时间，因为遍历j从0-sum才是最费时间的。