贪心算法实验报告

实验3贪心算法（定稿）第一篇：实验3 贪心算法（定稿）《算法设计与分析》实验报告实验3贪心算法姓名学号班级实验日期实验地点一、实验目的1、掌握贪心算法的设计思想。

2、理解最小生成树的相关概念。

二、实验环境1、硬件环境 CPU：酷睿i5 内存：4GB 硬盘：1T2、软件环境操作系统：Windows10 编程环境：jdk 编程语言：Java三、实验内容：在Prim算法与Kruskal算法中任选一种求解最小生成树问题。

1、你选择的是：Prim算法2、数据结构（1）图的数据结构——图结构是研究数据元素之间的多对多的关系。

在这种结构中，任意两个元素之间可能存在关系，即结点之间的关系可以是任意的，图中任意元素之间都可能相关。

图形结构——多个对多个，如（2）树的数据结构——树结构是研究数据元素之间的一对多的关系。

在这种结构中，每个元素对下(层)可以有0个或多个元素相联系，对上(层)只有唯一的一个元素相关，数据元素之间有明显的层次关系。

树形结构——一个对多个，如3、算法伪代码 Prim(G,E,W)输入：连通图G 输出：G的最小生成树T 1.S←{1};T=∅ 2.While V-S ≠∅ do3.从V-S中选择j使得j到S中顶点的边e的权最小；T←T∪{e}4.S←S∪{j}3、算法分析时间复杂度：O(n)空间复杂度：O(n^2)4、关键代码（含注释）package Prim;import java.util.*;publicclass Main { staticintMAXCOST=Integer.MAX_VALUE;staticint Prim(intgraph[][], intn){ /* lowcost[i]记录以i为终点的边的最小权值，当lowcost[i]=0时表示终点i加入生成树 */ intlowcost[]=newint[n+1];/* mst[i]记录对应lowcost[i]的起点，当mst[i]=0时表示起点i加入生成树 */ intmst[]=newint[n+1];intmin, minid, sum = 0;/* 默认选择1号节点加入生成树，从2号节点开始初始化*/ for(inti = 2;i<= n;i++){/* 标记1号节点加入生成树 */ mst[1] = 0;/* n个节点至少需要n-1条边构成最小生成树 */ for(inti = 2;i<= n;i++){/* 找满足条件的最小权值边的节点minid */ for(intj = 2;j<= n;j++){/* 输出生成树边的信息:起点，终点，权值 */System.out.printf(“%c1, minid + 'A''A' + 1;intj = chy-'A' + 1;graph[i][j] = cost;graph[j][i] = cost;for(intj = 1;j<= n;j++){ } graph[i][j] = MAXCOST;} } System.out.println(”Total:"+cost);} }5、实验结果（1）输入（2）输出最小生成树的权值为：生成过程：(a)(b)(d)(e)(c)四、实验总结（心得体会、需要注意的问题等）这次实验，使我受益匪浅。

实验3 贪心算法解活动安排问题一、实验要求1．要求按贪心法求解问题；2．要求读文本文件输入活动安排时间区间数据；3．要求显示结果。

二、实验仪器和软件平台仪器：带usb接口微机软件平台：WIN-XP + VC++6.0三、源程序#include "stdafx.h"#include<stdio.h>#include<stdlib.h>#include<algorithm>#define N 50#define TURE 1#define FALSE 0int s[N];/*开始时间*/int f[N];/*结束时间*/int A[N];/*用A存储所有的*/int Partition(int *b,int *a,int p,int r);void QuickSort(int *b,int *a,int p,int r);void GreedySelector(int n,int *s,int *f,int *A);int main(){int n=0,i;while(n<=0||n>50){printf("\n");printf("请输入活动的个数,n=");scanf("%d",&n);if(n<=0) printf("请输入大于零的数!");else if(n>50) printf("请输入小于50的数!");}printf("\n请分别输入开始时间s[i]和结束时间f[i]:\n\n");for(i=1;i<=n;i++){printf("s[%d]=",i,i);scanf("%d",&s[i]);printf("f[%d]=",i,i);scanf("%d",&f[i]);printf("\n");}QuickSort(s,f,1,n); //按结束时间非减序排列printf("按结束时间非减序排列如下:\n"); /*输出排序结果*/ printf("\n 序号\t开始时间结束时间\n");printf("-------------------------\n");for(i=1;i<=n;i++)printf(" %d\t %d\t %d\n",i,s[i],f[i]);printf("-------------------------\n");GreedySelector(n,s,f,A);//贪心算法实现活动安排printf("安排的活动序号依次为：");for(i=1;i<=n;i++){if(A[i])printf("\n%d %d-->%d",i,s[i],f[i]);}printf("\n");system("pause");return 0;}//快速排序void QuickSort(int *b,int *a,int p,int r){int q;if(p<r)q=Partition(b,a,p,r);QuickSort(b,a,p,q-1);/*对左半段排序*/ QuickSort(b,a,q+1,r);/*对右半段排序*/ }}//产生中间数int Partition(int *b,int *a,int p,int r){int k,m,y,i=p,j=r+1;int x=a[p];y=b[p];while(1){while(a[++i]<x);while(a[--j]>x);if(i>=j)break;else{k=a[i];a[i]=a[j];a[j]=k;m=b[i];b[i]=b[j];b[j]=m;}a[p]=a[j];b[p]=b[j];a[j]=x;b[j]=y;return j;}//贪心算法实现活动安排void GreedySelector(int n,int *s,int *f,int *A){//用集合A来存储所选择的活动A[1]=TURE; //默认从第一次活动开始执行int j=1; //j记录最近一次加入到A中的活动for(int i=2;i<=n;i++){//f[j]为当前集合A中所有活动的最大结束时间//活动i的开始时间不早于最近加入到集合A中的j的时间f[j]if(s[i]>=f[j]){A[i]=TURE; //当A[i]=TURE时，活动i在集合A中j=i;}else A[i]=FALSE; }}四、运行结果五、实验小结贪心算法总是做出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

贪心算法实验报告贪心算法实验报告引言：贪心算法是一种常用的算法设计策略，它通常用于求解最优化问题。

贪心算法的核心思想是在每一步选择中都选择当前最优的解，从而希望最终能够得到全局最优解。

本实验旨在通过实际案例的研究，探索贪心算法的应用和效果。

一、贪心算法的基本原理贪心算法的基本原理是每一步都选择当前最优解，而不考虑整体的最优解。

这种贪婪的选择策略通常是基于局部最优性的假设，即当前的选择对于后续步骤的选择没有影响。

贪心算法的优点是简单高效，但也存在一定的局限性。

二、实验案例：零钱兑换问题在本实验中，我们以零钱兑换问题为例，来说明贪心算法的应用。

问题描述：假设有不同面值的硬币，如1元、5元、10元、50元和100元，现在需要支付给客户x元，如何用最少的硬币数完成支付？解决思路：贪心算法可以通过每次选择当前面值最大的硬币来求解。

具体步骤如下：1. 初始化一个空的硬币集合，用于存放选出的硬币。

2. 从面值最大的硬币开始，如果当前硬币的面值小于等于待支付金额，则将该硬币放入集合中，并将待支付金额减去该硬币的面值。

3. 重复步骤2，直到待支付金额为0。

实验过程：以支付金额为36元为例，我们可以通过贪心算法求解最少硬币数。

首先，面值最大的硬币为100元，但36元不足以支付100元硬币，因此我们选择50元硬币。

此时，剩余待支付金额为36-50=-14元。

接下来，面值最大的硬币为50元，但待支付金额为负数，因此我们选择下一个面值最大的硬币，即10元硬币。

此时，剩余待支付金额为-14-10=-24元。

继续选择10元硬币，剩余待支付金额为-24-10=-34元。

再次选择10元硬币，剩余待支付金额为-34-10=-44元。

最后，选择5元硬币，剩余待支付金额为-44-5=-49元。

由于待支付金额已经为负数，我们无法继续选择硬币。

此时，集合中的硬币数为1个50元和3个10元，总共4个硬币。

实验结果：通过贪心算法，我们得到了36元支付所需的最少硬币数为4个。

贪心算法实验报告心得前言贪心算法是一种常见且重要的算法设计思想，通过每一步都选择当下最优的解决方案，以期望最终得到全局最优解。

在学习与实践贪心算法的过程中，我有了许多心得与体会。

什么是贪心算法？贪心算法是一种求解问题的算法思想，它的特点是每一步都选择当前最优的解决方案，而不考虑该选择对以后步骤的影响。

贪心算法通常适用于可以将问题分解为若干个子问题，并且通过每次选择当前最优解来得到整体最优解的情况。

贪心算法的基本步骤贪心算法的基本步骤可以总结为以下几个方面：1.确定问题的解空间，并找到问题的最优解。

贪心算法通常通过穷举法或者利用问题的特殊性质来确定解空间。

2.制定贪心策略。

贪心算法的核心是确定每一步选择的贪心策略，即选择当前最优解。

3.确定贪心策略的正确性。

贪心算法的一个关键问题是如何证明贪心策略的正确性。

可以通过数学证明、反证法或者举反例等方式来进行证明。

4.实现贪心算法。

将贪心策略转化为实际可执行的算法步骤，编写代码来求解问题。

贪心算法实验结果分析在本次实验中，我使用贪心算法解决了一个经典问题：找零钱问题（Change-Making Problem）。

给定一定面额的硬币和需找的金额，我们的目标是使用最少的硬币来完成找零钱。

贪心算法的思路是每次选择面额最大的硬币进行找零。

实验设计1.实验输入：我设计了多组输入来测试贪心算法的性能。

每组输入包括一个需找的金额和一个硬币集合。

2.实验输出：对于每组输入，贪心算法输出一个最优的硬币找零方案，以及使用的硬币数量。

3.实验评价：我使用了实际需找金额与贪心算法计算得到的找零金额的差值来评估算法的准确性，并统计了算法的时间复杂度。

实验结果从多组实验结果中可以观察到，贪心算法在大部分情况下给出了正确的找零金额，并且算法的时间复杂度较低。

结果分析贪心算法在找零钱问题中的应用是合理的。

每次选择面额最大的硬币进行找零，可以快速接近最优解，并且相对其他算法具有较低的时间复杂度。

数据优化算法实验报告1. 引言数据优化算法是在处理大规模数据时的重要工具。

随着数据量的增大和计算需求的增加，需要寻找更加高效的算法来处理和优化数据。

本实验旨在研究并比较两种常见的数据优化算法：贪心算法和动态规划算法。

通过实验比较它们在不同场景下的优化效果和性能。

2. 贪心算法贪心算法是一种简单而直观的算法。

其基本思想是每次选择局部最优解，并希望通过局部最优解的组合来达到全局最优解。

贪心算法能够在很短的时间内找到一个近似最优解，但不能保证一定得到最优解。

本实验中，我们以背包问题为例，使用贪心算法进行优化。

背包问题是在给定背包容量的情况下，选择一些物品放入背包，使得放入背包的物品总价值最大化。

贪心算法的核心思想是每次选择单位重量价值最大的物品放入背包。

实验结果表明，贪心算法在小规模问题上有着较好的效果，但在大规模问题上有可能得不到最优解。

这是因为贪心算法只考虑了当前局部最优解，没有考虑到全局最优解的可能性。

3. 动态规划算法动态规划算法是一种通过分别解决子问题并将解决方案合并来解决复杂问题的方法。

与贪心算法相比，动态规划算法更加追求全局最优解，但也需要更多的计算时间和空间。

同样以背包问题为例，使用动态规划算法进行优化。

动态规划算法的核心思想是将问题分解为子问题，通过递归地求解子问题的最优解，最后合并子问题的解来获得全局最优解。

在背包问题中，动态规划算法采用二维数组来存储每个子问题的最优解。

实验结果表明，动态规划算法能够在较短的时间内得到全局最优解，但对于大规模问题，算法的时间和空间复杂度会显著增加。

4. 实验对比和讨论通过实验对比，我们可以看到贪心算法和动态规划算法在不同场景下的优化效果和性能有所不同。

对于小规模问题，贪心算法能够快速计算得到一个近似最优解，并能在较短的时间内完成计算。

然而，贪心算法不能保证一定得到全局最优解，可能会得到次优解。

对于大规模问题，动态规划算法能够在较短的时间内得到全局最优解。

算法分析与设计实验报告第一次附加实验附录：完整代码（贪心法）//贪心算法最小生成树prim算法#include<iostream>#include<fstream>#include<string>#include<time.h>#include<iomanip>using namespace std;#define inf 9999; //定义无限大的值const int N=6;template<class Type> //模板定义void Prim(int n,Type c[][N+1]);int main(){int c[N+1][N+1];cout<<"连通带权图的矩阵为："<<endl;for(int i=1;i<=N;i++) //输入邻接矩阵{for(int j=1;j<=N;j++){cin>>c[i][j];}}cout<<"Prim算法最小生成树选边次序如下："<<endl;clock_t start,end,over; //计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();Prim(N,c); //调用Prim算法函数end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); //显示运行时间cout<<endl;system("pause");return 0;}template<class Type>//参数为结点个数n，和无向带权图中各结点之间的距离c[][N+1]void Prim(int n,Type c[][N+1]){Type lowcost[N+1]; //记录c[j][closest]的最小权值int closest[N+1]; //V-S中点j在s中的最临接顶点bool s[N+1]; //标记各结点是否已经放入S集合¦s[1]=true;//初始化s[i],lowcost[i],closest[i]for(int i=2;i<=n;i++){lowcost[i]=c[1][i];closest[i]=1;s[i]=false;}for(int i=1;i<n;i++){Type min=inf;int j=1;for(int k=2;k<=n;k++)//找出V-S中是lowcost最小的顶点j{if((lowcost[k]<min)&&(!s[k]))//如果k的lowcost比min小并且k结点没有被访问{min=lowcost[k]; //更新min的值j=k;}}cout<<j<<' '<<closest[j]<<endl; //输出j和最邻近j的点s[j]=true; //将j添加到s中for(int k=2;k<=n;k++){if((c[j][k]<lowcost[k])&&(!s[k]))//s集合放进j后更新各结点的lowcost 的值{lowcost[k]=c[j][k];closest[k]=j;}}}}。

一、实验背景贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是全局最好或最优的算法策略。

贪心算法并不保证能获得最优解，但往往能获得较好的近似解。

在许多实际应用中，贪心算法因其简单、高效的特点而被广泛应用。

本实验旨在通过编写贪心算法程序，解决经典的最小生成树问题，并分析贪心算法的优缺点。

二、实验目的1. 理解贪心算法的基本原理和应用场景；2. 掌握贪心算法的编程实现方法；3. 分析贪心算法的优缺点，并尝试改进；4. 比较贪心算法与其他算法在解决最小生成树问题上的性能。

三、实验内容1. 最小生成树问题最小生成树问题是指：给定一个加权无向图，找到一棵树，使得这棵树包含所有顶点，且树的总权值最小。

2. 贪心算法求解最小生成树贪心算法求解最小生成树的方法是：从任意一个顶点开始，每次选择与当前已选顶点距离最近的顶点，将其加入生成树中，直到所有顶点都被包含在生成树中。

3. 算法实现（1）数据结构- 图的表示：邻接矩阵- 顶点集合：V- 边集合：E- 已选顶点集合：selected- 最小生成树集合：mst（2）贪心算法实现```def greedy_mst(graph):V = set(graph.keys()) # 顶点集合selected = set() # 已选顶点集合mst = set() # 最小生成树集合for i in V:selected.add(i)mst.add((i, graph[i]))while len(selected) < len(V):min_edge = Nonefor edge in mst:u, v = edgeif v not in selected and (min_edge is None or graph[u][v] < graph[min_edge[0]][min_edge[1]]):min_edge = edgeselected.add(min_edge[1])mst.add(min_edge)return mst```4. 性能分析为了比较贪心算法与其他算法在解决最小生成树问题上的性能，我们可以采用以下两种算法：（1）Prim算法：从任意一个顶点开始，逐步添加边，直到所有顶点都被包含在生成树中。

贪心算法_实验报告一、设计分析●问题描述：键盘输入一个高精度的正整数N（N不超过240位），去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。

编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。

●设计思路：在位数固定的前提下，让高位的数字尽量小其值就较小，依据此贪心策略解决此问题。

删除高位较大的数字。

具体：相邻两位比较若高位比低位大则删除高位。

删除字符的方法：1）物理删除，用后面的字符覆盖已删除的字符。

有比较多字符移动操作，算法效率不高。

2）用数组记录字符的状态，“1”表示对应数字存在，“0”表示对应数字已删除。

3）利用数组，记录未删除字符的下标：n=“1 2 4 3 5 8 3 3”0 0 0 0 0 04比3大删除“1 2 3 5 8 3 3” 1 2 4 5 0 08比3大删除“1 2 3 5 3 3” 1 2 4 5 05比3大删除“1 2 3 3 3” 1 2 4 7 8二、程序代码c语言实现#include<stdio.h>#include<string.h>#define N 10000int main(void){char a[N];int i,j,k,n;printf("输入要处理的数据：\n");gets(a);printf("输入要删除的数字个数：\n");scanf("%d",&n);三、测试用例四、实验总结加深了对贪心算法的理解与运用。

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。