算法分析与设计实验报告--贪心法 (2)

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

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

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

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

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

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

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

问题描述：假设有不同面值的硬币，如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. 实验对比和讨论通过实验对比，我们可以看到贪心算法和动态规划算法在不同场景下的优化效果和性能有所不同。

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

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

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

算法分析与设计实验报告第 5 次实验使用贪心法求出给定图各点的最短路径，并计算算法的执行时间，分析算法的有效性。

已知一个有向网络 G=(V,E)和源点 V1，如上所示，求出从源点出发到图中其余顶点的最短路径。

1 用邻接矩阵表示有向图，并进行初始化，同时选择源点；}手动输入实现实验所给图形：随机数产生图的权值：通过这次实验，我回顾了回溯法求解最短路径问题，在其中加入了舍伍德附录：完整代码#include<stdio.h>#include<stdlib.h>#include<time.h>#define maxint 1000int c[200][200]={0};void Dijkstra(int n,int v,int dist[],int prev[]){ bool s[maxint];for(int i=1;i<=n;i++){dist[i]=c[v][i];s[i]=false;if(dist[i]==maxint) prev[i]=0;else prev[i]=v;} //找到第一个可行源点 s[]标志，记录prev[]前一个点dist[v]=0;s[v]=true;for(int i=1;i<n;i++){int temp=maxint;int u=v;for(int j=1;j<=n;j++){if((!s[j])&&(dist[j]<temp)){u=j;temp=dist[j];}}s[u]=true;for(int j=1;j<=n;j++){int newdist=dist[u]+c[u][j];if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}}}}int main(){int n,v;printf("请输入顶点数： ");scanf("%d",&n);//printf("路径： ");srand(time(0));for(int i=1;i<n+1;i++){for(int j=1;j<n+1;j++){/* scanf("%d",&c[i][j]);*/ ///手动输入if(i!=j){if((c[j][i]==0)||(c[j][i]==1000))c[i][j]=rand()%100+1;else c[i][j]=1000;if(c[i][j]>50) c[i][j]=1000;}}}printf("请输入源点： ");scanf("%d",&v);int dist[n+1],prev[n+1];printf("\n路径：\n");for(int i=1;i<n+1;i++){for(int j=1;j<n+1;j++)printf("%5d ",c[i][j]);printf("\n");}Dijkstra(n,v,dist,prev);for(int i=1;i<n+1;i++){printf("\n%d到%d的最短路径为：%d",v,i,dist[i]);}}。

《算法设计与分析》课程实验报告实验序号：07实验项目名称：实验8 贪心算法（一）一、实验题目1.删数问题问题描述：键盘输入一个高精度的正整数N（不超过250 位），去掉其中任意k个数字后剩下的数字按原左右次序将组成一个新的非负整数。

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

若输出前有0则舍去2.区间覆盖问题问题描述：设x1,x2,...xn是实轴上的n个点。

用固定长度为k的闭区间覆盖n个点，至少需要多少个这样的固定长度的闭区间？请你设计一个有效的算法解决此问题。

3.会场安排问题问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。

设计一个有效的贪心算法进行安排。

（这个问题实际上是著名的图着色问题。

若将每一个活动作为图的一个顶点，不相容活动间用边相连。

使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。

）4.导弹拦截问题问题描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

给定导弹依次飞来的高度（雷达给出的高度数据是≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

二、实验目的（1）通过实现算法，进一步体会具体问题中的贪心选择性质，从而加强对贪心算法找最优解步骤的理解。

（2）掌握通过迭代求最优的程序实现技巧。

（3）体会将具体问题的原始数据预处理后（特别是以某种次序排序后），常能用贪心求最优解的解决问题方法。

三、实验要求（1）写出题1的最优子结构性质、贪心选择性质及相应的子问题。

（2）给出题1的贪心选择性质的证明。

（3）（选做题）：写出你的算法的贪心选择性质及相应的子问题，并描述算法思想。

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

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

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

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

二、实验目的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算法：从任意一个顶点开始，逐步添加边，直到所有顶点都被包含在生成树中。

实验三课程名称：算法设计与实现实验名称：贪心算法-找零问题实验日期：2019年5月2日仪器编号：007班级：数媒0000班姓名：郝仁学号0000000000实验内容假设零钱系统的币值是{1，p,p^2,……，p^n},p>1,且每个钱币的重量都等于1，设计一个最坏情况下时间复杂度最低的算法，使得对任何钱数y，该算法得到的零钱个数最少，说明算法的主要设计思想，证明它的正确性，并给出最坏情况下的时间复杂度。

实验分析引理1（离散数学其及应用3.1.4）：若n是正整数，则用25美分、10美分、5美分和1美分等尽可能少的硬币找出的n美分零钱中，至多有2个10美分、至多有1个5美分、至多有4个1美分硬币，而不能有2个10美分和1个5美分硬币。

用10美分、5美分和1美分硬币找出的零钱不能超过24美分。

证明如果有超过规定数目的各种类型的硬币，就可以用等值的数目更少的硬币来替换。

注意，如果有3个10美分硬币，就可以换成1个25美分和1个5美分硬币；如果有2个5美分硬币，就可以换成1个10美分硬币；如果有5个1美分硬币，就可以换成1个5美分硬币；如果有2个10美分和1个5美分硬币，就可以换成1个25美分硬币。

由于至多可以有2个10美分、1个5美分和4个1美分硬币，而不能有2个10美分和1个5美分硬币，所以当用尽可能少的硬币找n美分零钱时，24美分就是用10美分、5美分和1美分硬币能找出的最大值。

假设存在正整数n，使得有办法将25美分、10美分、5美分和1美分硬币用少于贪心算法所求出的硬币去找n美分零钱。

首先注意，在这种找n美分零钱的最优方式中使用25美分硬币的个数q′，一定等于贪心算法所用25美分硬币的个数。

为说明这一点，注意贪心算法使用尽可能多的25美分硬币，所以q′≤q。

但是q′也不能小于q。

假如q′小于q，需要在这种最优方式中用10美分、5美分和1美分硬币至少找出25美分零钱。

而根据引理1，这是不可能的。

贪心算法_实验报告一、设计分析●问题描述：键盘输入一个高精度的正整数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);三、测试用例四、实验总结加深了对贪心算法的理解与运用。

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

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

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

淮海工学院计算机工程学院实验报告书课程名：《算法分析与设计》题目：实验3 贪心算法班级：学号：姓名：实验3 贪心算法实验目的和要求（1）了解前缀编码的概念，理解数据压缩的基本方法；（2）掌握最优子结构性质的证明方法；（3）掌握贪心法的设计思想并能熟练运用（4）证明哈夫曼树满足最优子结构性质；（5）设计贪心算法求解哈夫曼编码方案；（6）设计测试数据，写出程序文档。

实验内容设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为{w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。

实验环境Turbo C 或VC++实验学时2学时，必做实验数据结构与算法//构造哈夫曼结构体struct huffman{double weight; //用来存放各个结点的权值int lchild,rchild,parent; //指向双亲、孩子结点的指针 };核心源代码#include<iostream>#include <string>using namespace std;#include <stdio.h>//构造哈夫曼结构体struct huffman{double weight;∑=j i k k aint lchild,rchild,parent;};static int i1=0,i2=0;//选择权值较小的节点int Select(huffman huff[],int i){int min=11000;int min1;for(int k=0;k<i;k++){if(huff[k].weight<min && huff[k].parent==-1){min=huff[k].weight;min1=k;}}huff[min1].parent=1;return min1;}//定义哈夫曼树，并对各个节点进行赋权值void HuffmanTree(huffman huff[],int weight[],int n) {for(int i=0;i<2*n-1;i++){huff[i].lchild=-1;huff[i].parent=-1;huff[i].rchild=-1;}for(int l=0;l<n;l++){huff[l].weight=weight[l];}for(int k=n;k<2*n-1;k++){int i1=Select(huff,k);int i2=Select(huff,k);huff[i1].parent=k;huff[i2].parent=k;huff[k].weight= huff[i1].weight+huff[i2].weight;huff[k].lchild=i1;huff[k].rchild=i2;}}//哈夫曼编码，左0右1void huffmancode(huffman huff[],int n){string s;int j;for(int i=0;i<n;i++){s="";j=i;while(huff[j].parent!=-1){if(huff[huff[j].parent].lchild==j)s=s+"0";else s=s+"1";j=huff[j].parent;}cout<<"第"<<i+1<<"个节点的哈夫曼编码为：";for(int j=s.length();j>=0;j--){cout<<s[j];}cout<<endl;}}void main(){huffman huff[20];int n,w[20];printf("请输入节点的个数:");scanf("%d",&n);for(int i=0;i<n;i++){printf("请输入第%d个节点的权值:",i+1);scanf("%d",&w[i]);}printf("\n");HuffmanTree(huff,w,n);huffmancode(huff,n);}实验结果实验体会本次实验是用贪心法求解哈夫曼编码,其实贪心法和哈夫曼树的原理是一样的,每次将集合中两个权值最小的二叉树合并成一棵新二叉树，每次选择两个权值最小的二叉树时，规定了较小的为左子树。

一、实验目的通过本次实验，使学生对贪心算法的概念、基本要素、设计步骤和策略有更深入的理解，掌握贪心算法的原理和应用，并能够运用贪心算法解决实际问题。

二、实验内容本次实验主要涉及以下两个问题：1. 使用贪心算法解决单起点最短路径问题；2. 使用贪心算法解决小船过河问题。

三、实验原理1. 贪心算法贪心算法（又称贪婪算法）是一种在每一步选择中都采取当前最优的选择，从而希望导致结果是全局最优的算法。

贪心算法在每一步只考虑当前的最优解，不保证最终结果是最优的，但很多情况下可以得到最优解。

2. 单起点最短路径问题单起点最短路径问题是指在一个有向无环图中，从某个顶点出发，找到到达其他所有顶点的最短路径。

3. 小船过河问题小船过河问题是指一群人需要划船过河，船只能容纳两个人，过河后需要一人将船开回，问最少需要多久让所有人过河。

四、实验步骤及说明1. 创建图结构，包括顶点数组和边信息。

2. 使用Dijkstra算法求解单起点最短路径问题，得到最短路径和前驱顶点。

3. 使用贪心算法找到两点之间的最短距离，并更新距离和前驱顶点信息。

4. 遍历所有顶点，找到未纳入已找到点集合的距离最小的顶点，并更新其距离和前驱顶点。

5. 最终输出从源顶点到达其余所有点的最短路径。

6. 使用贪心算法解决小船过河问题，按照以下步骤进行：（1）计算所有人过河所需的总时间；（2）计算每次划船往返所需时间；（3）计算剩余人数；（4）重复（2）和（3）步骤，直到所有人过河。

五、实验结果与分析1. 单起点最短路径问题实验中，我们选取了有向无环图G，其中包含6个顶点和8条边。

使用贪心算法和Dijkstra算法求解单起点最短路径问题，得到的实验结果如下：- 贪心算法求解单起点最短路径问题的时间复杂度为O(V^2)，其中V为顶点数；- Dijkstra算法求解单起点最短路径问题的时间复杂度为O(V^2)，其中V为顶点数。

2. 小船过河问题实验中，我们选取了一群人数为10的人过河，船每次只能容纳2人。

贪心算法实验小结
最近，我和我的同学们在实验室里进行了一次关于贪心算法的实验，探究贪心算法在旅行商问题中的应用。

实验的准备工作非常简单，我们只需要准备好实验所需的数据，并将其输入到计算机中即可。

之后，我们使用贪心算法来解决这个旅行商问题，运用贪心思想，在遍历所有城市时，选择当前停留时间最短的城市作为下一站，以期最终获得最短的旅行路线。

实验的过程中，我们发现，贪心算法可以有效地解决旅行商问题，即使在城市数量较多的情况下，它仍然能够在较短的时间内得到最优解。

除了旅行商问题之外，贪心算法还可以应用于其他许多其他问题，比如背包问题，最大化问题等。

在这次实验中，我们研究到了贪心算法的原理和应用，对于贪心算法在求解复杂问题中的重要性有了更深的认识。

此外，我们也体会到了贪心算法的局限性，它只能获得局部最优解，而不能保证全局最优解。

总之，本次实验对我们的研究有很大的帮助，不仅加深了对贪心算法的认识，而且还能够更好地理解其在实际问题中的应用，让我们更加清楚如何有效地利用贪心算法来解决复杂问题。