实验三贪心算法.doc

实验三 贪心算法(4学时)一、设计目的1） 理解多机调度问题；2） 理解贪心法解决问题的基本思路；3） 掌握多机调度问题的贪心法；4） 掌握小根堆在多机调度问题的贪心法中的应用。二、 设计内容1 任务描述(多机调度问题描述)2 主要数据类型与变量JobNode类：MachineNode类：(主要描述成员及含义)3 主要程序模块贪心算法描述：主程序：三、 测试a) 方案n=7,m=3,ID=1，2，3，4，5，6，7,time=2，14，4，16，6，5，3n为作业个数，m为机器台数，ID数组存放作业编号，time数组存放对应ID数组中相应编号的作业处理时间。b) 结果结合测试数据实例描述测试过程和测试结果，最好给出表示测试过程和结果的抓图，对测试结果进行分析并得出结论。结果：总的加工时间为：17四、 总结与讨论可针对本设计谈体会、谈改进、谈设想等，展示你的概括、归纳和创新思维能力，看重的不是你的对与错，而是鼓励你的创新思维。归纳贪心法求解问题的一般思想及关键：贪心策略：贪心选择性质：最优子结构性质：贪心法与动态规划法的区别：附：程序模块的源代码#include #include using namespace std;ifstream fin(input.txt);ofstream fout(output.txt);/template void Swap(Type& x,Type& y)Type temp=x;x=y;y=temp;/template void Sort(Type* a,int n) /对a1.n中n个元素进行排序(选择排序?)for(int i=1;in;i+)int k=i;for(int j=i+1;j=n;j+) /找出第i小的元素if(ajak) k=j;Swap(ai,ak);template class MinHeap public: MinHeap(int ms); MinHeap(); void Insert(const Type& x); void DeleteMin(Type& x); protected: void FilterDown();/自顶向下构造堆 void FilterUp();/自底向上构造堆 private: Type *heap; int length;/template MinHeap:MinHeap(int m)heap=new Typem+1;length=0;/template void MinHeap:Insert(const Type& x)heap+length=x;FilterUp();/template template void MinHeap:FilterUp()/自底向上进行调整int i=length,j=i/2;/父节点的编号Type temp=heapi;while(i1)if(temp=heapj)break;/找到了相应的位置elseheapi=heapj;i=j;j=i/2;heapi=temp;/template void MinHeap:DeleteMin(Type &x)x=heap1;heap1=heaplength;length-;FilterDown();/template void MinHeap:FilterDown()int i=1,j=i*2;Type temp=heapi; while(j=length)if(jheapj+1) j+;/如果左右子树都存在,找出最小者,用j标记 if(tempheapj) break;/找到了相应的位置elseheapi=heapj;i=j;j=2*i;heapi=temp;/template MinHeap:MinHeap()delete heap;/class JobNodefriend void Greedy(JobNode*,int,int);friend void main(void);public:operator int() const return time;private:int ID,time;class MachineNodefriend void Greedy(JobNode*,int,int);public:operator int() constreturn avail;private:int ID,avail;/template void Greedy(Type a,int n,int m)if(n=m)cout 为每个作业分配一台机器.endl;return;Sort(a,n);MinHeap H(m);MachineNode x;for(int i=1;i=1;i-)H.DeleteMin(x);cout将机器x.ID从x.avail到