問題描述:

用2臺處理機A和B處理n個作業(yè)。設(shè)第i個作業(yè)交給機器A處理時需要時間ai，若由機器B來處理，則需要時間bi。由于各作業(yè)的特點和機器的性能關(guān)系，很可能對于某些i，有ai>bi，而對于某些j,j≠i，有aj>bj。既不能將一個作業(yè)分開由2臺機器處理，也沒有一臺機器能同時處理2個作業(yè)。設(shè)計一個動態(tài)規(guī)劃算法，使得這2臺機器處理完這n個作業(yè)的時間最短(從任何一臺機器開工到最后一臺機器停工的總時間)。對于給定的2臺處理機A和B處理n個作業(yè)，找出一個最優(yōu)調(diào)度方案，使2臺機器處理完這n個作業(yè)的時間最短。

算法講解：

?一、首先，搞懂p是干嘛的，二維數(shù)組p存儲的內(nèi)容到底是什么

1、p數(shù)組的列坐標(biāo)k記錄n個作業(yè)，橫坐標(biāo)t是a機器單獨處理所需要的時間 *

2、p數(shù)組元素值來記錄加上b機器后，每次添加一個作業(yè)后，在a機器單獨處理的每個時刻上加上b后的最優(yōu)解?

3、p數(shù)組是一列一列更新的，即每次增加一個作業(yè)，在不同的時間下，b機器的最優(yōu)用時 *

二、所以每次更新的值就是兩種情況：

?1、新加入的k作業(yè)，當(dāng)用時t<a[k]時，說明此時a機器根本無法處理k，只能是b來處理，所以就是直接更新p[t][k]的值為p[t][k-1]+b[k]; *

2、新加入的k作業(yè)，t>=a[k]時，此時a機器有直接處理k的能力，所以就要進行比較，比較的雙方就是

?(1)a不處理k，b接著在t時刻，k-1次作業(yè)后繼續(xù)處理k(也就是情況1) p[t][k]=p[t][k-1]+b[k];

?(2)a處理k，b此時的值就直接繼承:a處理k用時后的剩余時間(t-a[k])，對應(yīng)的前k-1個作業(yè)的用時 p[t][k]=p[t-a[k]][k-1]; *

三、動態(tài)更新完p數(shù)組之后，我們就得到了最后一列的值?

1、橫坐標(biāo)t結(jié)合數(shù)組內(nèi)元素值p[t][n]分別是t時間內(nèi)a機器單獨處理用時 和b機器在a機器處理的基礎(chǔ)上最優(yōu)用時 ，說白了就是橫坐標(biāo)t就是a單獨處理a的用時，p內(nèi)值就是a、b并行工作后b的最優(yōu)用時 2、分別比較每一行的兩個數(shù)值，記錄每一行的最大值，用一個變量min記錄所有最大值的最小值，就得到了最優(yōu)解

研究一個實例：(a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4)。

（給張圖片，Excel搞的，沒畫完，只畫了前三列，不過應(yīng)該已經(jīng)足夠你理解了，豎著一列一列的畫，最重要的還是搞懂p里面記錄的到底是什么，橫坐標(biāo)t到底是什么）

?

?代碼如下：

#include<bits/stdc++.h>
using namespace std;
#define MAXTIME 500
int p[MAXTIME][MAXTIME];

int Dynamic(int a[],int b[],int n){
    int aTime = 0;//作業(yè)僅在機器a上運行是所需要的時間
    for(int k = 1;k<=n;k++){//從1開始，到n，方便操作
        aTime += a[k];//記錄此時a機器單獨操作需要的最大時間
        for(int t = 0;t<=aTime;t++){//一列一列的更新
            if(t<a[k]){//此時時間條件不允許a單獨處理k
                p[t][k]=p[t][k-1]+b[k];//此處p元素值直接是b處理完k-1后繼續(xù)處理k
            } else{//此時時間條件允許a處理新加入的k，進行比較
                p[t][k]=p[t-a[k]][k-1]>p[t][k-1]+b[k]?p[t][k-1]+b[k]:p[t-a[k]][k-1];
            }
        }
    }
    int minTime = 999999;
    for(int t = 0;t<aTime;t++){
        int maxt = max(t,p[t][n]);//找到每個時間段對應(yīng)的兩者的最大值
        minTime = minTime>maxt?maxt:minTime;//minTime每次更新，記錄最小值
    }//說白了就是橫坐標(biāo)t就是a單獨處理a的用時，p內(nèi)值就是a、b并行工作后b的最優(yōu)用時
    //在考慮到所有作業(yè)時，比較最后一列每一行兩者的大小就能得到最優(yōu)用時
    return minTime;
}
int main(){
    int n;//n個作業(yè)
    cin >> n; //讀入作業(yè)個數(shù)
    int a[n+1];
    int b[n+1];
    for(int i=1;i<=n;i++)//讀入機器A運行時間
        cin >> a[i];
    for(int i=1;i<=n;i++)//讀入機器B運行時間
        cin >> b[i];
    int minTime = Dynamic(a,b,n);
    cout << minTime;
    return 0;
}
/*
 * 算法描述:
 * 一、首先，搞懂p是干嘛的，二維數(shù)組p存儲的內(nèi)容到底是什么
 * 1、p數(shù)組的列坐標(biāo)k記錄n個作業(yè)，橫坐標(biāo)t是a機器單獨處理所需要的時間
 * 2、p數(shù)組元素值來記錄加上b機器后，每次添加一個作業(yè)后，在a機器單獨處理的每個時刻上加上b后的最優(yōu)解
 * 3、p數(shù)組是一列一列更新的，即每次增加一個作業(yè)，在不同的時間下，b機器的最優(yōu)用時
 * 二、所以每次更新的值就是兩種情況：
 * 1、新加入的k作業(yè)，當(dāng)用時t<a[k]時，說明此時a機器根本無法處理k，只能是b來處理，所以就是直接更新p[t][k]的值為p[t][k-1]+b[k];
 * 2、新加入的k作業(yè)，t>=a[k]時，此時a機器有直接處理k的能力，所以就要進行比較，比較的雙方就是
 *   (1)a不處理k，b接著在t時刻，k-1次作業(yè)后繼續(xù)處理k(也就是情況1)  p[t][k]=p[t][k-1]+b[k];
 *   (2)a處理k，b此時的值就直接繼承:a處理k用時后的剩余時間(t-a[k])，對應(yīng)的前k-1個作業(yè)的用時 p[t][k]=p[t-a[k]][k-1];
 * 三、動態(tài)更新完p數(shù)組之后，我們就得到了最后一列的值
 * 1、橫坐標(biāo)t結(jié)合數(shù)組內(nèi)元素值p[t][n]分別是t時間內(nèi)a機器單獨處理用時 和b機器在a機器處理的基礎(chǔ)上最優(yōu)用時
 *    說白了就是橫坐標(biāo)t就是a單獨處理a的用時，p內(nèi)值就是a、b并行工作后b的最優(yōu)用時
 * 2、分別比較每一行的兩個數(shù)值，記錄每一行的最大值，用一個變量min記錄所有最大值的最小值，就得到了最優(yōu)解
*/

運行結(jié)果如下：

?

?文章來源地址http://www.zghlxwxcb.cn/news/detail-756070.html

到了這里，關(guān)于獨立任務(wù)的最優(yōu)調(diào)度問題（動態(tài)規(guī)劃）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！