0026算法笔记——【贪心算法】多机调度问题

《0026算法笔记——【贪心算法】多机调度问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、问题描述   设有n个独立的作业{1,2,…,n},由m台相同的机器进行加工处理.作业i所需时间为ti.约定:任何作业可以在任何一台机器上加工处理,但未完工前不允许中断处理,任何作业不能拆分成更小的子作业。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。    多机调度问题是一个NP完全问题，到目前为止还没有完全有效的解法。对于这类问题，用贪心选择策略有时可以设计出一个比较好的近似算法。   2、贪心算法求解思路   采用最长处理时间作业优先的贪心策略:   当n≤m时,只要将机器i的[0,ti]时间区间分配给作业i即可。   当n>m时,将n个作业依

2、其所需的处理时间从大到小排序,然后依次将作业分配给空闲的处理机。   具体代码如下：   (1)MinHeap.h[cpp] viewplain copy1.#include   2.using namespace std;  3.template  4.class MinHeap  5.{  1.    private:  2.        T *heap; //元素数组，0号位置也储存元素  3.        int CurrentSize; //目前元素个数  4.        int MaxSize; //可容纳的最多元素个数  5.  6

3、.        void FilterDown(const int start,const int end); //自上往下调整，使关键字小的节点在上  7.        void FilterUp(int start); //自下往上调整  8.  9.    public:  10.        MinHeap(int n=1000);  11.        ~MinHeap();  12.        bool Insert(const T &x); //插入元素  13.  14.        T RemoveMin(); //删除最小元素  15.        T G

4、etMin(); //取最小元素  16.  17.        bool IsEmpty() const;  18.        bool IsFull() const;  19.        void Clear();  20.};  21.  22.template  23.MinHeap::MinHeap(int n)  24.{  25.    MaxSize=n;  26.    heap=new T[MaxSize];  27.    CurrentSize=0;  28.}  29.  30.template  31.MinHe

5、ap::~MinHeap()  32.{  33.    delete []heap;  34.}  35.  36.template  37.void MinHeap::FilterUp(int start) //自下往上调整  38.{  39.    int j=start,i=(j-1)/2; //i指向j的双亲节点  40.    T temp=heap[j];  41.  42.    while(j>0)  43.    {  1.        if(heap[i]<=temp)  2.            break;  3.        

6、else  4.        {  5.            heap[j]=heap[i];  6.            j=i;  7.            i=(i-1)/2;  8.        }  9.    }  10.    heap[j]=temp;  11.}  12.  13.template  14.void MinHeap::FilterDown(const int start,const int end) //自上往下调整，使关键字小的节点在上  15.{  16.    int i=start,j=2*i+1;  17.    

7、T temp=heap[i];  18.    while(j<=end)  19.    {  20.        if( (jheap[j+1]) )  21.            j++;  22.        if(temp<=heap[j])  23.            break;  24.        else  25.        {  26.