算法分析-任务调度-动态规划

老师让讲算法题，没带书纸，学校电脑也没Markdown软件。先将思路写在这里。

任务调度问题

假设房前有两个处理机A、B，以及n个待处理的任务。第i个任务在处理处理机A上处理需要的时间为ai，在处理机B上处理的时间为bi，两个处理机可以并行处理任务，但单个处理机不能同时执行任务。要求给定n个任务及各个任务对应的ai 、bi，求得顺序完成这些任务所需要的最短时间。

问题分析

这个问题是动态规划部分的习题，需利用动态规划思想求解。开始思路有点混乱，看了网上的一些讲解，都不甚明了，现在我自己按照动态规划的一般步骤来分析一下。

动态规划分析步骤

1.分析最优解结构，找出最优解的结构性质与特征

首先是如何搜索最优解，就是如何构造表格的问题。我们这样定义，

有二位数组R，假设横轴（ROW）为机器A的所用的处理时间，纵轴（COL）是当前完成的任务数。R[ROW][COL]是在A所用时间为ROW 下完成前COL个任务，B机器所用的最少时间。

定义：R[r][c] 是机器A用时为r的情况下，完成前c个任务，B机器的最少用时

接下来就是分析最优子结构，即如何填充表格：

对于以上定义，假设有k个任务，k为大于1的整数,对于任意time_A, A[i],B[i] 分别为A、B机器完成第i个任务所需的时间。

现在来讨论 R[time_A][k]的值，

如果 time_A > A[k] ，假设第k个任务是A来做，那么当前B的最少用时就等于在A用时time_A 的情况下，完成 k - 1 个任务的最少用时。即： R[time_A][k] = R[ time_A - A[k] ][k - 1]；如果第k个任务是B来做，那么当前B的最少用时，就等于A用时time_A的情况下，完成k - 1 个任务B的最少用时加上B完成第k个任务所需时间，即 R[time_A][k] = R[ time_A ][k - 1] + B[i]。

如果 time_A < A[k], 那么第K个任务只能由B完成，则与上面的第二种情况相同，有 R[time_A][k] = R[ time_A ][k - 1] + B[i]。

于是得到递归关系：

$$
\begin{eqnarray*}
{如果 time_A < A[k]:}\hspace{10.8cm}\
{
R[time_A][k] =
\begin{cases}
{R[time_A - A[k] ][k - 1]}&{k由A做}\
{R[time_A][k - 1] + B[i]}&{k由B做}
\end{cases}
} \tag{1} \
{
{如果 time_A >= A[k]:} \
\hspace{5cm}R[time_A][k] =
{R[time_A][k - 1] + B[i]}{\ \ \ \ \ }{k由B做}
} \tag{2} \
\end{eqnarray*}
$$
填好所有得格子以后，最后一行就是完成K个任务，A耗时[0：MAX_TIME]之间，B得最短用时，在这一行里面找一个最理想的值，即min（max(R[time_A][k] , time_A) )

可以得到c实现

#include <iostream>
#include <iomanip>

#define MX 400

using namespace std;

void alg3(int* res,int A[],int B[],int N,int ALL_TIME);
int sum(int* A,int N);


int main(){
    int N = 31;
    int A[100] = {0,6 ,7 ,7 ,4 ,4 ,2 ,9 ,5 ,3 ,8 ,9 ,1 ,5 ,10 ,10 ,5 ,8, 7 ,6 ,1 ,6 ,7 ,3 ,10, 6, 3 ,1 ,3 ,10 ,5 ,4 ,10 ,10 ,9 ,9 ,5 ,9 ,3 ,10 ,8 };
    int B[100] = {0,2 ,7 ,9 ,7 ,10, 5, 3, 2, 8, 4, 8, 10, 8, 6, 9 ,2 ,2, 7, 4, 2, 7, 5, 2, 3, 3, 1 ,2 ,6 ,5 ,10 ,1 ,9 ,7 ,5 ,4 ,3 ,1 ,2 ,10 ,1  };
    int ALL_TIME = sum(A,N);
    int res = 0xFFFF;
    // cout <<res;
    alg3(&res,A,B,N - 1,ALL_TIME);
    return 0;
}
/**
 * 每一次只增加一个任务，先全部让B机器去做，然后逐步增加A的时间，在A的最大容纳限度内，将任务逐渐转移给A。
 * 到最后任务数为N时，当前A用的时间和B用的时间最长的就是该任务序列的最长时间。只需要找到A和B最小的排列即该任务的最优解。
 */

void alg3(int* res,int A[],int B[],int N,int ALL_TIME){
    // 二维数组 (m[完成任务数][所耗时间]) => 在该条件下，B所耗时间 
    int m[N + 1][MX] = {0};
    if (A[1] > B[1]){
        m[1][0] = B[1];
    }
    for (int i = 1; i <= N;i++){
        // 遍历 A 机器可能用的所有时间 **模拟时间流逝**
        for (int j = 0;j < MX;j++){
            if (j > A[i])// 如果 A有足够时间了，那就让它做，可不能让它闲着
            {
                // 虽然你能做这个工作，但是我要看看，你做的好不好
                if (m[i - 1][j - A[i]] < m[i - 1][j] + B[i]) 
                {
                     m[i][j] = m[i - 1][j - A[i]];
                }else{
                    m[i][j] = m[i - 1][j] + B[i];
                }
            }else // 不然，就只能让机器B背锅了，能者多劳
            {
                m[i][j] = B[i] + m[i - 1][j];
            }
        }
    }


    int tmp = 0xFFFFFF;
    for(int i = 0;i <= ALL_TIME;i++)
    {
        if (m[N][i] < tmp && i < tmp)
        {
            tmp = m[N][i] > i ? m[N][i] : i;
        }
    }
    cout << tmp;
}


int sum(int *A,int N){
    int sum = 0;
    for (int i = 0;i < N;i++){
        sum += A[i];
    }
    return sum;
}

第二种填充方法

将表格为

Author: 哒琳

Permalink: http://blog.jieis.cn/2021/cc3c1996-652b-4ac5-a880-55e06c5edb36.html

updated at 2021-06-25

# algorithm

任务调度问题

算法分析-任务调度-动态规划

任务调度问题

问题分析

动态规划分析步骤

第二种填充方法

Comments