算法设计和分析——非单位时间任务安排问题——状态转移方程的讲解和源码——为什么动态规划可以使用矩阵进行实现！

可以使用矩阵进行实现！"/>

算法设计和分析——非单位时间任务安排问题——状态转移方程的讲解和源码——为什么动态规划可以使用矩阵进行实现！

文章目录

• • • • 题目描述（这里为了方便演示，直接改成控制台输入和输出）
      • 回顾动态规划的基本要素和框架
      • 根据回顾进行问题的解决
      • 具体的问题分析
      • 一个错误的样例模仿，你可以看一下，可以参考一下，采用顺序时间轴解决这个问题是错误的
      • 错误的结论
      • 纠正之后的解释
      • 实现的源代码
      • 总结和分析
      • 花了好几天，总算有点理解了！

题目描述（这里为了方便演示，直接改成控制台输入和输出）

问题描述:具有截止时间和误时惩罚的任务安排问题可描述如下:

• (1）给定n个任务的集合S={1,2,…,n};

• (2）完成任务i需要ti ( 1≤i≤n）时间;

• (3）任务i的截止时间di ( 1si≤n），即要求任务i在时间di之前结束;

• (4）任务i的误时惩罚wi ( 1si≤n)，即任务i未在时间di之前结束，将招致wi的惩罚;若按时完成，则无惩罚。

• 任务安排问题要求确定S的一个时间表（最优时间表）使得总误时惩罚达到最小。

• 算法设计:对于给定的n个任务，计算总误时惩罚最小的最优时间表。

• 数据输入:由文件input.txt给出输入数据。第1行是1个正整数n，表示任务数。接下来的n行中，每行有3个正整数a,b,c，表示完成相应任务需要时间a,截止时间为b，误时惩罚值为c。

    输入样例：7			1 4 702 2 601 4 501 3 401 1 301 4 203 6 80输出样例：110
  

回顾动态规划的基本要素和框架

• 三种性质：
  • 最优子结构性质：当前问题的最优解一定包含的子问题的最优解。通过子问题的最优解，可以推导出当前问题的最优解
  • 无后效性：某阶段一旦确定，就不受之后每个阶段决策的影响
  • 重复子问题性质：子问题要重复计算很多次
• 解的模型：
  • 多阶段决策最优解模型
  • 首先讲问题分阶段进行解决，并且每一个阶段一定存在一个最优解的情况

根据回顾进行问题的解决

• 三种性质：
  • 最优子结构性质：七个任务的最小惩罚，一定是包含6个任务的最小惩罚，这是显而易见的
  • 无后效性：第六个任务的取了最低耗时的情况，不会影响第七个任务的执行
  • 重复子问题性质：凡是在第一任务之后的调用，都会调用到第一个任务的执行结论
• 多阶段决策最优解模型：
  • 将任务的分配划分成按时间点进行，然后选择执行不同任务阶段划分问题。
  • 当前时间点，随着任务的执行不断向前推进，然后每个时间点选择不同的任务去执行。
  • 轮到某个任务之后，会有以下几种选择：
    • 做：上一个时间段的最优选择
    • 不做：上一个时间段的最优选择+ 当前任务超期的惩罚

具体的问题分析

• 首先为了保证所有任务执行完毕之后，惩罚最小，所以要尽量保证不被惩罚。所有任务都尽量要在截至时间之前完成。所以要将所有任务按照截至时间从小到大进行排序，并且在必须惩罚得情况下，选择惩罚最小的去执行。
• 对样例进行排序之后，输出的结果如下
  

一个错误的样例模仿，你可以看一下，可以参考一下，采用顺序时间轴解决这个问题是错误的

• 我们先仿照这类似的任务安排的算法题，复制一下对应的状态转移方程，然后在进行修改！具体参考
  
• 二维矩阵中的值的每一个值一定要有比较的意义，独立任务最有调度问题比较的是执行的总时间，非单位时间任务安排问题比较的是惩罚值，因为是要求取最小的惩罚值。
• 确定一个任务能否顺利执行，就是要确定当前时间和截止时间以及工作时间的关系：
• 当前时间一定要确保比最迟开始时间小，当前任务才有可能顺利执行
  
• 按照时间轴，直接和当前任务的最迟开始时间进行比较，然后在进行判定，具体详见下图，可比较的过程

• 根据上述定义，可以推出状态转移方程，如下图

• 注明：说是那么说的，其实这个状态转移的方程从来没有推出来过，这里只是试着去解释一下，让他变得好理解！

错误的结论

• 注意哈，时间轴类型动态规划只能解决所有任务的调度的最短的时间，对于最终结果不是问时间的，应该使用单任务的时间分配，不是整个时间轴的问题

纠正之后的解释

• 这里是对应任务序号的时间分配，时间轴是相对于单个任务而言的，不是相对于整体的任务而言的
  
• 状态转移方程主要是针对当前的第i个任务而言，分配的时间也是针对第i个任务而言的，不是所有的任务，具体的状态转移方程的如下图
  

因为会产生无用的时间，故就要在选择最短的时间的时候，确定最小值的情况

实现的源代码

/*描述：非单位时间任务安排问题参数：num是任务的数量work是每个任务需要的工作时间deadline是每一个任务的结束时间Punishment是每个任务的惩罚时间返回：返回最小的惩罚书数
*/
int UnunitArrangement(int num, int work[], int deadline[], int PunishTime[]) {//基本思路：//首先得避免惩罚，将截止时间按照从小到大得序列进行排序，保证不会出现惩罚得情况//然后，在一定会被惩罚的情况下，确保选择惩罚最小的去执行//针对刚才的思路分析：我们外界大体上使用动态规划，然后局部进行贪心算法的选择//首先将截止时间按照从小到大的顺序进行排列，int Atemp = 0, BTemp = 0, CTemp = 0;for (int i = 0; i < num - 1; ++i){for (int j = 0; j < num - i - 1; ++j){//截至的时间为比较的标准，然后三者数组全部进行交换if (deadline[j] > deadline[j + 1]) {//交换截止时间Atemp = deadline[j + 1];deadline[j + 1] = deadline[j];deadline[j] = Atemp;//交换工作时间BTemp = work[j + 1];work[j + 1] = work[j];work[j] = BTemp;//交换惩罚量CTemp = PunishTime[j + 1];PunishTime[j + 1] = PunishTime[j];PunishTime[j] = CTemp;}}}cout << "排序之后任务详情是：" << endl;cout << "截止时间       需要时间       惩罚大小" << endl;for (int i = 0; i < num; i++) {cout << "  "<<deadline[i] << "               " << work[i] << "                 " << PunishTime[i] << endl;cout<<"修改之后最迟开始时间！"<<endl;deadline[i] = deadline[i] - work[i];}//初始化一个二维矩阵，用来进行动态规划，横坐标是分配给第i个任务的工作时间，纵坐标是任务的序号int** Dynamic = new int* [num];for (int i = 0; i < num + 1; ++i){//所有任务都完成要是一个工作时间Dynamic[i] = new int[num];//将所有的值都初始化为零memset(Dynamic[i],0,sizeof(int)*num);}//动态规划应该是求出惩罚代价最小的情况//p表示惩罚的代价，使代价最小，p就是当前时间的当前任务的最小惩罚时间//状态转移方程：p( i , d ) = min{ p(i-1, d)+wi ， p(i-1, min{d, di}-ti) }//状态意义表示：p （i，d）=p（i-1，d）+wi  表示第i个任务，的执行时间大于该//所有任务的工作时间都是小于最后一个任务的截至时间的，因为已经按照从小到大进行排序了for (int i = 0; i < num; ++i){//分配给第一个任务的时间是小于对应第一个任务需要的时间if (i < work[0]){//分配给第一个任务的时间小于第一个任务执行的时间,第一个任务是没有办法顺利执行的Dynamic[0][i] = PunishTime[0];}else {//分配给第一个任务的时间大于第一个任务的执行时间，第一个任务可以顺利的执行Dynamic[0][i] = 0;}}//每一次都检查输出cout<<"第一个任务完成之后的输出："<<endl;showBorad(Dynamic);//处理第一个任务之后的任务int x, y;for (int i = 1; i < num; ++i){//只需要遍历到最后一个任务的截至时间就行了for (int j = 0; j < num; ++j){//当前任务也就是第i个任务，是不执行，原先的惩罚加上当前的惩罚x = Dynamic[i - 1][j] + PunishTime[i];if (j < deadline[i]){//当前的任务Dynamic[i][j] = x;}else {//当前任务也就是第i-1个任务，执行，惩罚就是执行第i个任务完成之前的惩罚//选择当前时间和截至时间最小的去执行，然后减去对应工作时间//最终的结果就是每个任务必须开始的最迟的时间截点y = Dynamic[i - 1][min(j, deadline[i]) - work[i]];//当前的任务可以做，可以不做Dynamic[i][j] = min(x, y);}}cout<<"后续每个任务完成的情况！"<<endl;showBorad(Dynamic);}//返回最后一个任务完成时间的惩罚return Dynamic[num - 1][deadline[num - 1]];}

总结和分析

• 对于给类似的任务安排问题，现如今已经遇到了两类问题，纵轴不怎么变，大部分都是关于横轴和对应二维矩阵的某点的意义的变化！
  • 第一类，最终所求涉及到时间，而且任务是顺序执行的，所以横坐标是对应所有任务执行的顺序的时间轴。第一类问题传送门
  • 第二类，最终求的最小的惩罚，任务是随即执行的，所以横坐标是针对单个任务进行分配的工作时间。这类问题的样例，就是当前这道题。
• 以前一直对状态转移方程，为什么总是直接去当前列的上一行或者上一行的某一列感到困惑，现在理解了！
  • 最优子结构性质，就规定了，当前问题的最优解一定包含了上一个子问题的最优解。如果要解决当前问题最优解，就要再上一个问题的最优解基础上！
  • 无后效性和重复子问题，主要是规定某一行之内的各个数据是分别根据上一行的各个情况做出的最好的决策！
  • 综上所述，所以整个矩阵行与行之间的转变是最优子问题之间的转变，列与列之间是确保最优解的在本行的不同状态的合理分布！

花了好几天，总算有点理解了！

• 这是快考试了，复习才有的感悟，从背包问题中得来的，是上一个状态减去当前要装的物体的重量的装填对应的价值，不是上一个物体不装。懂吗？