贪心算法实验二要点分析.docx

实验二贪心选择算法姓名：田圆圆学号：2013125135一、实验目的与要求：理解贪心选择算法的思想。二、预习与准备：贪心选择算法思想：（1）贪心选择能得到问题的最优解，要证明我们所做的第一步选择一定包含在一个最优解总，即存在一个最优解的第一步是从我们的贪心选择开始。（2）在做出第一步贪心选择后剩下的子问题应该是和原问题类似的规模较小的子问题为此我们可以用数学归纳法来证明贪心选择能得到问题的最优解。三、实验题目：1.在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。 2.背包问题给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?3.多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。四、实验过程：1.用贪心算法求单元最短路径问题：其中，dist[i]：表示当前从源到顶点i的最短特殊路径长度。实验代码为：#include iostream#include stdio.h#include limits.husing namespace std;const int V = 9; //定义顶点个数//从未包含在SPT的集合T中，选取一个到S集合的最短距离的顶点。int getMinIndex(int dist[V], bool sptSet[V]) { int min = INT_MAX, min_index; for (int v = 0; v V; v++) if (sptSet[v] == false dist[v] min) min = dist[v], min_index = v; return min_index;}// 打印结果void printSolution(int dist[], int n) {printf(Vertex Distance from Source\n);for (int i = 0; i V; i++)printf(%d \t\t %d\n, i, dist[i]);}//source 代表源点void dijkstra(int graph[V][V], int source) {int dist[V]; // 存储结果，从源点到 i的距离bool sptSet[V]; // sptSet[i]=true 如果顶点i包含在SPT中// 初始化. 0代表不可达for (int i = 0; i V; i++){dist[i] = (graph[source][i] == 0 ? INT_MAX:graph[source][i]);sptSet[i] = false;}// 源点，距离总是为0. 并加入SPTdist[source] = 0;sptSet[source] = true;// 迭代V-1次，因此不用计算源点了，还剩下V-1个需要计算的顶点。for (int count = 0; count V - 1; count++) {// u，是T集合中，到S集合距离最小的点int u = getMinIndex(dist, sptSet);// 加入SPT中sptSet[u] = true;//更新到V的距离。可以理解为Bellman-Ford中的松弛操作for (int v = 0; v V; v++)if (!sptSet[v] graph[u][v] dist[u] != INT_MAX dist[u] + graph[u][v] dist[v])dist[v] = dist[u] + graph[u][v];}printSolution(dist, V);}int main() {/* 以例子中的图为例 */int graph[V][V] ={ { 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 },{ 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);r