贪心算法实验二报告

1、实验二 贪心选择算法姓名 ： 田圆圆 学号：2013125135一、实验目的与要求： 理解贪心选择算法的思想。二、预习与准备：贪心选择算法思想：（1）贪心选择能得到问题的最优解，要证明我们所做的第一步选择一定包含在一个最优解总，即存在一个最优解的第一步是从我们的贪心选择开始。（2）在做出第一步贪心选择后剩下的子问题应该是和原问题类似的规模较小的子问题à为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。三、实验题目：1.在无向图 G=(V,E) 中，假设每条边 Ei 的长度为 wi，找到由顶点 V0 到其余各点的最短路径。 2.背包问题给定n种物品和一个背包。物品i的重量是Wi

2、，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?3.多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。四、实验过程：1.用贪心算法求单元最短路径问题：其中，disti：表示当前从源到顶点i的最短特殊路径长度。实验代码为：#include <iostream>#include <stdio.h>#include <limits.h>using namespace std;con

3、st int V = 9; /定义顶点个数/从未包含在SPT的集合T中，选取一个到S集合的最短距离的顶点。int getMinIndex(int distV, bool sptSetV) int min = INT_MAX, min_index; for (int v = 0; v < V; v+) if (sptSetv = false && distv < min) min = distv, min_index = v; return min_index;/ 打印结果void printSolution(int dist, int n) printf("

4、;Vertex Distance from Sourcen");for (int i = 0; i < V; i+)printf("%d tt %dn", i, disti);/source 代表源点void dijkstra(int graphVV, int source) int distV; / 存储结果，从源点到 i的距离bool sptSetV; / sptSeti=true 如果顶点i包含在SPT中/ 初始化. 0代表不可达for (int i = 0; i < V; i+)disti = (graphsourcei = 0 ? INT_M

5、AX:graphsourcei);sptSeti = false;/ 源点，距离总是为0. 并加入SPTdistsource = 0;sptSetsource = true;/ 迭代V-1次，因此不用计算源点了，还剩下V-1个需要计算的顶点。for (int count = 0; count < V - 1; count+) / u，是T集合中，到S集合距离最小的点int u = getMinIndex(dist, sptSet);/ 加入SPT中sptSetu = true;/更新到V的距离。可以理解为Bellman-Ford中的松弛操作for (int v = 0; v < V

6、; v+)if (!sptSetv && graphuv && distu != INT_MAX&& distu + graphuv < distv)distv = distu + graphuv;printSolution(dist, V);int main() /* 以例子中的图为例 */int graphVV = 0, 4, 0, 0, 0, 0, 0, 8, 0 , 4, 0, 8, 0, 0, 0, 0, 11, 0 , 0, 8, 0, 7, 0, 4, 0, 0, 2 , 0, 0, 7, 0, 9, 14, 0, 0, 0

7、, 0, 0, 0, 9, 0, 10, 0, 0, 0 , 0, 0, 4, 0, 10, 0, 2, 0, 0 , 0, 0, 0, 14, 0, 2, 0, 1, 6 , 8, 11, 0, 0, 0, 0, 1, 0, 7 , 0, 0, 2, 0, 0, 0, 6, 7, 0 ;dijkstra(graph, 0);return 0;2. 背包问题： #include<stdio.h> int f10100; /构造最优矩阵 void package0_1(int *w,int *v,int n,int c) int i,j; /初始化矩阵 for(i=1;i<=n

8、;i+) fi0 = 0; for(j=1;j<=c;j+) f0j = 0; for(i=1;i<=n;i+) for(j=1;j<=c;j+) /当容量够放入第i个物品，并且放入之后的价值要比不放大 if(wi <= j && fi-1j-wi + vi > fi-1j) fij = fi-1j-wi + vi; else fij = fi-1j; printf("最大价值: %d n",fnc); /构造最优解 void getResult(int n,int c,int *res,int *v,int *w) int i

9、,j; j = c; for(i=n;i>=1;i-) if(fij != fi-1j) resi = 1; j = j - wi; void main() int w6 = 0,2,2,6,5,4;/每个物品的重量 int v6 = 0,6,3,5,4,6;/每个物品的价值 int res5 = 0,0,0,0,0; int n = 5; /物品的个数 int c = 10; /背包能容的重量 int i,j; package0_1(w,v,n,c); for(i=0;i<=n;i+) for(j=0;j<=c;j+) printf("%2d ",fij

10、); printf("n"); getResult(n,c,res,v,w); printf("放入背包的物品为: n"); for(i=1;i<=n;i+) if(resi = 1) printf("%d ",i); 3. 多机器调配问题：#include "stdafx.h" #include "MinHeap.h" #include <iostream> #include <fstream> using namespace std; const int N =

11、 7;/作业个数 const int M = 3;/机器台数 ifstream fin("4d7.txt"); class JobNode /friend void Greedy(JobNode ,int,int); /friend int main(void); public: operator int() const return time; /private: int ID,time; ; class MachineNode /friend void Greedy(JobNode ,int,int); public: operator int() const retu

12、rn avail; /private: int ID,avail; ; template<class Type> void Greedy(Type a,int n,int m); template<class Type> void SelectSort(Type a,int n); int main() JobNode aN+1 ;/各作业所需要的处理时间 cout<<"各作业所需要的处理时间为："<<endl; for(int i=1; i<=N; i+) fin>>ai.ID>>ai.time

13、; cout<<"ID:"<<ai.ID<<",time:"<<ai.time<<endl; Greedy(a,N,M); return 0; template<class Type> void Greedy(Type a,int n,int m) if(n<=m)/机器数量比作业数量多，直接分配 cout<<"直接为每个作业分配一台机器."<<endl; return; SelectSort(a,n);/排序，从大到小 MinHea

14、p<MachineNode> H(m); MachineNode x; for(int i=1; i<=m; i+) x.avail = 0; x.ID = i; H.Insert(x); for(int i=1; i<=n; i+) x = H.RemoveMin(); cout<<"将机器"<<x.ID<<"从"<<x.avail<<"到" <<(x.avail+ai.time)<<"的时间段分配给作业"

15、 <<ai.ID<<endl; x.avail += ai.time; H.Insert(x);/根据新的avail值将x插入Heap中适当位置 template<class Type> void SelectSort(Type a,int n) Type temp; int max; for(int i=1;i<n;i+) max=i; for(int j=i+1;j<=n;j+) if(amax<aj) max=j; if(max != i) temp = ai; ai = amax; amax = temp; /4d7 贪心算法 多机

16、调度问题#include "stdafx.h"#include "MinHeap.h"#include <iostream> #include <fstream> using namespace std; const int N = 7;/作业个数const int M = 3;/机器台数ifstream fin("4d7.txt");class JobNode/friend void Greedy(JobNode ,int,int);/friend int main(void);public:operator

17、 int() constreturn time;/private:int ID,time;class MachineNode/friend void Greedy(JobNode ,int,int);public:operator int() constreturn avail;/private:int ID,avail;template<class Type> void Greedy(Type a,int n,int m);template<class Type> void SelectSort(Type a,int n);int main()JobNode aN+1

18、 ;/各作业所需要的处理时间cout<<"各作业所需要的处理时间为："<<endl;for(int i=1; i<=N; i+)fin>>ai.ID>>ai.time;cout<<"ID:"<<ai.ID<<",time:"<<ai.time<<endl;Greedy(a,N,M);return 0;template<class Type> void Greedy(Type a,int n,int m)if(n

19、<=m)/机器数量比作业数量多，直接分配cout<<"直接为每个作业分配一台机器."<<endl;return;SelectSort(a,n);/排序，从大到小MinHeap<MachineNode> H(m);MachineNode x;for(int i=1; i<=m; i+)x.avail = 0;x.ID = i;H.Insert(x);for(int i=1; i<=n; i+)x = H.RemoveMin();cout<<"将机器"<<x.ID<<&

20、quot;从"<<x.avail<<"到"<<(x.avail+ai.time)<<"的时间段分配给作业"<<ai.ID<<endl;x.avail += ai.time;H.Insert(x);/根据新的avail值将x插入Heap中适当位置template<class Type> void SelectSort(Type a,int n)Type temp; int max; for(int i=1;i<n;i+) max=i; for(int j=i+1;j<=n;j+) if(amax<aj) max=j; if(max != i