算法分析与设计实验报告——独立任务最优调度问题

一、 实验目的

掌握动态规划的基本思想和解决问题的基本步骤，认识动态规划和分治法的联系与区别，对比解决同一问题的两种算法设计策略的时间复杂性。

二、实验要求

用c++语言实现用动态规划算法解决独立任务最优调度问题，分析时间复杂性，体会动态规划算法解决问题的基本思路和步骤。

三、 实验原理

独立任务最优调度问题具有最优子结构性质。先计算m=max{max{a_i},max{b_i}}，设布尔量p(i，j，k)表示前k个作业可以在处理机A用时不超过i时间且在处理机B用时不超过j时间内完成。递归方程如下：

p(i，j，k)=p( i-a_k，j，k-1 )|p( i，j-b_k，k-1 )

则最短时间为min{max{i，j}}。

四、 实验过程(步骤)

见附件一
实验步骤、特点
重要源代码（流操作的部分要醒目的提示并注释）

五、 运行结果

见附件二

六、实验分析与讨论

一开始没有想到用三维数组来解决，没有思路，经过查阅资料才明白了这个问题的动态规划算法。三维数组的创建与释放对我来说也是一个问题。最后都是查找了很多资料才解决的。
遇到的问题，及解决方案

七、实验特色与心得

这次试验掌握了独立任务最优调度问题的动态规划的基本思想和解决问题的基本步骤，充分认识了动态规划和分治法的联系与区别，还分析了此算法的时间复杂度为O(m²n²)，再次提高了自己的能力。

附件一 实验过程(步骤)

// Created by DZX on 2020/12/3.
//独立任务最优调度问题
#include "bits/stdc++.h"
using namespace std;
int n, m, mn, MiniTime;
int *a;
int *b;
int ***p;
void Make3DArray(int ***&x, int rows, int cols, int k) {
    //创建3维数组
    x = new int **[rows];
    for (int i = 0; i < rows; i++) {
    
        x[i] = new int *[cols];
        for (int j = 0; j < cols; j++)
            x[i][j] = new int[k];
    }
}
void Free3DArray(int ***&x, int rows, int cols, int k) {
    //释放3维数组
    for (int i = 0; i < rows; ++i) {
    
        for (int j = 0; j < cols; ++j) {
    
            free(x[i][j]);
        }
        free(x[i]);
    }
    free(x);
}
void init() {
    //初始化，输入数据创建数组
    cin >> n;
    m = 0;
    a = new int[n];
    b = new int[n];
    for (int i = 0; i < n; i++) {
    
        cin >> a[i];
        if (a[i] > m)
            m = a[i];
    }
    for (int i = 0; i < n; i++) {
    
        cin >> b[i];
        if (b[i] > m)
            m = b[i];
    }
    mn = m * n;
    Make3DArray(p, mn + 1, mn + 1, n + 1);
}
void dtgh() {
    //执行动态规划算法
    int i, j, k;
    //初始化三维数组
    for (i = 0; i <= mn; i++) {
    
        for (j = 0; j <= mn; j++) {
    
            p[i][j][0] = true;
            for (k = 1; k <= n; k++)
                p[i][j][k] = false;
        }
    }
    for (k = 1; k <= n; k++) {
    //执行动态规划递归
        for (i = 0; i <= mn; i++) {
    
            for (j = 0; j <= mn; j++) {
    
                if (i - a[k - 1] >= 0)
                    p[i][j][k] = p[i - a[k - 1]][j][k - 1];
                if (j - b[k - 1] >= 0)
                    p[i][j][k] = (p[i][j][k] || p[i][j - b[k - 1]][k - 1]);
            }
        }
    }
    for (i = 0, MiniTime = mn; i <= mn; i++) {
     //计算最优值
        for (j = 0; j <= mn; j++) {
    
            if (p[i][j][n]) {
    
                int tmp = (i > j) ? i : j;
                if (tmp < MiniTime)
                    MiniTime = tmp;
            }
        }
    }
    cout << "完成全部作业所需最短时间："<<MiniTime << endl;
}
void free() {
    //释放申请的空间
    Free3DArray(p, mn + 1, mn + 1, n + 1);
    free(a);
    free(b);
}
int main() {
    //主程序
    init();
    dtgh();
    free();
    return 0;
}
/*
6 15
2 5 7 10 5 2
3 8 4 11 3 4
 */

附件二 运行结果