贪心法的编程实验
- 格式:pptx
- 大小:1.10 MB
- 文档页数:46
贪心算法实验报告贪心算法实验报告引言:贪心算法是一种常用的算法设计策略,它通常用于求解最优化问题。
贪心算法的核心思想是在每一步选择中都选择当前最优的解,从而希望最终能够得到全局最优解。
本实验旨在通过实际案例的研究,探索贪心算法的应用和效果。
一、贪心算法的基本原理贪心算法的基本原理是每一步都选择当前最优解,而不考虑整体的最优解。
这种贪婪的选择策略通常是基于局部最优性的假设,即当前的选择对于后续步骤的选择没有影响。
贪心算法的优点是简单高效,但也存在一定的局限性。
二、实验案例:零钱兑换问题在本实验中,我们以零钱兑换问题为例,来说明贪心算法的应用。
问题描述:假设有不同面值的硬币,如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.实验评价:我使用了实际需找金额与贪心算法计算得到的找零金额的差值来评估算法的准确性,并统计了算法的时间复杂度。
实验结果从多组实验结果中可以观察到,贪心算法在大部分情况下给出了正确的找零金额,并且算法的时间复杂度较低。
结果分析贪心算法在找零钱问题中的应用是合理的。
每次选择面额最大的硬币进行找零,可以快速接近最优解,并且相对其他算法具有较低的时间复杂度。
贪心算法几个经典例子c语言1. 零钱兑换问题题目描述:给定一些面额不同的硬币和一个总金额,编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能够凑出总金额,返回 -1。
贪心策略:每次选择面额最大的硬币,直到凑出总金额或者无法再选择硬币为止。
C语言代码:int coinChange(int* coins, int coinsSize, int amount){int count = 0;for(int i = coinsSize - 1; i >= 0; i--){while(amount >= coins[i]){amount -= coins[i];count++;}}return amount == 0 ? count : -1;}2. 活动选择问题题目描述:有 n 个活动,每个活动都有一个开始时间和结束时间,选择一些活动使得它们不冲突,且能够参加的活动数最多。
贪心策略:每次选择结束时间最早的活动,直到所有活动都被选择或者无法再选择为止。
C语言代码:typedef struct{int start;int end;}Activity;int cmp(const void* a, const void* b){return ((Activity*)a)->end - ((Activity*)b)->end;}int maxActivities(Activity* activities, int n){qsort(activities, n, sizeof(Activity), cmp);int count = 1;int end = activities[0].end;for(int i = 1; i < n; i++){if(activities[i].start >= end){count++;end = activities[i].end;}}return count;}3. 跳跃游戏题目描述:给定一个非负整数数组,你最初位于数组的第一个位置。
算法分析与设计实验报告第 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]);}}。
一、实验背景贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择,从而希望导致结果是全局最好或最优的算法策略。
贪心算法并不保证能获得最优解,但往往能获得较好的近似解。
在许多实际应用中,贪心算法因其简单、高效的特点而被广泛应用。
本实验旨在通过编写贪心算法程序,解决经典的最小生成树问题,并分析贪心算法的优缺点。
二、实验目的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,这是不可能的。
实验三贪心算法实验目的1. 掌握贪心法的基本思想方法;2. 了解适用于用贪心法求解的问题类型,并能设计相应贪心法算法;3. 掌握贪心算法复杂性分析方法分析问题复杂性。
预习与实验要求1. 预习实验指导书及教材的有关内容,掌握贪心法的基本思想;2. 严格按照实验内容进行实验,培养良好的算法设计和编程的习惯;3. 认真听讲,服从安排,独立思考并完成实验。
实验设备与器材硬件:PC机软件:C++或Java等编程环境实验原理有一类问题是要从所有的允许解中求出最优解,其策略之一是“贪心法”,即逐次实施“贪心选择”:在每个选择步骤上做出的选择都是当前状态下最优的。
贪心选择依赖于在此之前所做出的选择,但不依赖于后续步骤所需要的选择,即不依赖于后续待求解子问题。
显然,这种选择方法是局部最优的,但不是从问题求解的整体考虑进行选择,因此不能保证最后所得一定是最优解。
贪心法是求解问题的一种有效方法,所得到的结果如果不是最优的,通常也是近似最优的。
实验内容以下几个问题选做一项:1. 用贪心法实现带有期限作业排序的快速算法应用贪心设计策略来解决操作系统中单机、无资源约束且每个作业可在等量时间内完成的作业调度问题。
假定只能在一台机器上处理N个作业,每个作业均可在单位时间内完成;又假定每个作业i都有一个截止期限di>0(它是整数),当且仅当作业i在它的期限截止以前被完成时,则获得pi的效益。
这个问题的一个可行解是这N个作业的一个子集合J,J中的每个作业都能在各自的截止期限之前完成。
可行解的效益值是J中这些作业的效益之和,即Σp。
具有最大效益值的可行解就是最优解。
2. 实现K元归并树贪心算法两个分别包含n个和m个记录的已分类文件可以在O(n+m)时间内归并在一起而得到一个分类文件。
当要把两个以上的已分类文件归并在一起时,可以通过成对地重复归并已分类的文件来完成。
例如:假定X1,X2,X3,X4是要归并的文件,则可以首先把X1和X2归并成文件Y1,然后将Y1和X3归并成Y2,最后将Y2和X4归并,从而得到想要的分类文件;也可以先把X1和X2归并成Y1,然后将X3和X4归并成Y2,最后归并Y1和Y2而得到想要的分类文件。
c++贪心算法经典例题和详解贪心算法(Greedy Algorithm)是一种优化问题解决方法,其基本思想是每一步都选择当前状态下的最优解,以期望达到全局最优解。
贪心算法的特点是每一步都要做出一个局部最优的选择,而这些局部最优选择最终构成了全局最优解。
下面是一个经典的贪心算法例题以及详解:例题:活动选择问题(Activity Selection Problem)假设有一个需要在同一时段使用同一个资源的活动集合,每个活动都有一个开始时间和结束时间。
设计一个算法,使得能够安排最多数量的互不相交的活动。
# 输入:-活动的开始时间数组`start[]`。
-活动的结束时间数组`end[]`。
# 输出:-选择的互不相交的活动的最大数量。
# 算法详解:1. 首先,将活动按照结束时间从小到大排序。
2. 选择第一个活动,并将其加入最终选择的集合中。
3. 对于剩下的活动,选择下一个结束时间最早且与前一个活动不冲突的活动。
4. 重复步骤3,直到所有活动都被选择。
```cpp#include <iostream>#include <algorithm>#include <vector>using namespace std;// 定义活动结构体struct Activity {int start, end;};// 比较函数,用于排序bool compareActivities(Activity a, Activity b) {return a.end < b.end;}// 贪心算法解决活动选择问题void activitySelection(vector<Activity>& activities) {// 按照结束时间排序sort(activities.begin(), activities.end(), compareActivities);// 第一个活动总是被选中cout << "Selected activity: (" << activities[0].start << ", " << activities[0].end << ")" << endl;// 选择其余活动int lastSelected = 0;for (int i = 1; i < activities.size(); i++) {// 如果当前活动的开始时间大于等于上一个选择的活动的结束时间,则选择该活动if (activities[i].start >= activities[lastSelected].end) {cout << "Selected activity: (" << activities[i].start << ", " << activities[i].end << ")" << endl;lastSelected = i;}}}int main() {vector<Activity> activities = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};cout << "Activities before sorting:" << endl;for (const Activity& activity : activities) {cout << "(" << activity.start << ", " << activity.end << ") ";}cout << endl;activitySelection(activities);return 0;}```在这个例子中,我们首先定义了一个活动的结构体`Activity`,然后编写了一个比较函数`compareActivities` 用于排序。
淮海工学院计算机工程学院实验报告书课程名:《算法分析与设计》题目:实验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人。
贪心算法实验小结
最近,我和我的同学们在实验室里进行了一次关于贪心算法的实验,探究贪心算法在旅行商问题中的应用。
实验的准备工作非常简单,我们只需要准备好实验所需的数据,并将其输入到计算机中即可。
之后,我们使用贪心算法来解决这个旅行商问题,运用贪心思想,在遍历所有城市时,选择当前停留时间最短的城市作为下一站,以期最终获得最短的旅行路线。
实验的过程中,我们发现,贪心算法可以有效地解决旅行商问题,即使在城市数量较多的情况下,它仍然能够在较短的时间内得到最优解。
除了旅行商问题之外,贪心算法还可以应用于其他许多其他问题,比如背包问题,最大化问题等。
在这次实验中,我们研究到了贪心算法的原理和应用,对于贪心算法在求解复杂问题中的重要性有了更深的认识。
此外,我们也体会到了贪心算法的局限性,它只能获得局部最优解,而不能保证全局最优解。
总之,本次实验对我们的研究有很大的帮助,不仅加深了对贪心算法的认识,而且还能够更好地理解其在实际问题中的应用,让我们更加清楚如何有效地利用贪心算法来解决复杂问题。
算法设计与分析实验报告实验名称贪心算法实现背包问题评分实验日期年月日指导教师姓名专业班级学号一.实验要求1. 优化问题有n个输入,而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成,而把满足约束条件的子集称为该问题的可行解。
可行解一般来说是不唯一的。
那些使目标函数取极值(极大或极小)的可行解,称为最优解。
2.贪心法求优化问题算法思想:在贪心算法中采用逐步构造最优解的方法。
在每个阶段,都作出一个看上去最优的决策(在一定的标准下)。
决策一旦作出,就不可再更改。
作出贪心决策的依据称为贪心准则(greedy criterion)。
3.一般方法1)根据题意,选取一种量度标准。
2)按这种量度标准对这n个输入排序3)依次选择输入量加入部分解中。
如果当前这个输入量的加入,不满足约束条件,则不把此输入加到这部分解中。
procedure GREEDY(A,n) /*贪心法一般控制流程*///A(1:n)包含n个输入//solutions←φ //将解向量solution初始化为空/for i←1 to n dox←SELECT(A)if FEASIBLE(solution,x)then solutions←UNION(solution,x)endifrepeatreturn(solution)end GREEDY4. 实现典型的贪心算法的编程与上机实验,验证算法的时间复杂性函数。
二.实验内容1. 编程实现背包问题贪心算法。
通过具体算法理解如何通过局部最优实现全局最优,并验证算法的时间复杂性。
2.输入5个的图的邻接矩阵,程序加入统计prim算法访问图的节点数和边数的语句。
3.将统计数与复杂性函数所计算比较次数比较,用表格列出比较结果,给出文字分析。
三.程序算法1.背包问题的贪心算法procedure KNAPSACK(P,W,M,X,n)//P(1:n)和W(1;n)分别含有按P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值和重量。
实验2、《贪心算法实验》一、实验目的1. 了解贪心算法思想2. 掌握贪心法典型问题,如背包问题、作业调度问题等。
二、实验内容1. 编写一个简单的程序,实现单源最短路径问题。
2. 编写一段程序,实现找零。
【问题描述】当前有面值分别为2角5分,1角,5分,1分的硬币,请给出找n分钱的最佳方案(要求找出的硬币数目最少)。
3. 编写程序实现多机调度问题【问题描述】要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m 台机器加工处理完成。
约定,每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理。
作业不能拆分成更小的子作业。
三、算法思想分析1.初始化将源点设计为红点集,其余点设计为蓝点,重复选择蓝点集中与源点路径最短的点加入红点集,更新剩余的蓝点集路径,直至蓝点集为空或者只剩下没有连通的点,那么源点到其余所有点的最短路径就出来了。
2.找零问题是典型的贪心问题,但是并不代表所有的找零都能用贪心算法找到最优解。
只有满足贪心选择性质的找零才能找到最优解,本题满足贪心选择性质,直接先一直选面值最大的硬币,再一次减小即可。
3.先对作业按时长进行重排序,再依次找目前用时最短的机器安排工作并加上对应时长,最后总时长为机器中用时最长的那个时长。
四、实验过程分析1.单源最短路径的算法思想并不难,但是在实际编码过程中还是有很多小问题需要注意,首先,一定要新建数组存储路径变化,因为后面计算路径时会用到原数组,如果直接在原数组上更改后面就找不到原数据了,那么就会出现偏差。
其次就是建议先写个伪代码,判断的if-else语句比较多,容易搞混,在代码中一定要及时备注,某些代码的功能是什么,不然再次看代码时需要思考很久甚至忘记。
2.找零问题直接用while循环或者不断取余取模即可解决。
3.作业调度问题大致分为三步,一是排序,二是不断找最短时长的机器安排作业,三是找最长时间为作业完成时间。
五、算法源代码及用户屏幕1.(1)算法源码/**********************单源最短路径问题。
实验三:贪心算法一、实验目的(1)理解贪心算法的基本思想;(2)熟悉多机调度问题的算法;(3)初步掌握贪心算法的应用。
二、实验环境微型计算机,WindowXP , Visual C++6.0三、实验内容要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。
约定每个作业均可在任何一台机器上加工处理,但未完工前不允许中断处理。
作业不能拆分成更小的子作业。
四、实验结果五、源代码#include <stdio.h>#define M 100void main(){int i,j,k,temp,m,n;int t[M]={2,14,4,16,6,5,3},p[M]={1,2,3,4,5,6,7},s[M],d[M]={0};m=3;n=7;for(i=0;i<7;i++)for(j=0;j<7-i;j++)if(t[j]<t[j+1]) //排序使t[]由大到小{temp=t[j];t[j]=t[j+1];t[j+1]=temp;temp=p[j]; //p[]始终和t[]一一对应p[j]=p[j+1];p[j+1]=temp;}for(i=0;i<m;i++) //求时间。
{s[i]=p[i];d[i]=t[i];}for(k=0;k<m;k++)printf(" %d",d[k]);printf("\n");for(i=m;i<n;i++){for(k=0;k<m-1;k++) //求最小。
{temp=d[k];if(temp>d[k+1]){temp=d[k+1];j=k+1;}}printf("这是最小下标的:%d\n",j);printf("最小的值:%d\n",temp);for(k=0;k<m;k++)printf(" %d",d[k]);printf("\n");//j=temp;s[j]=s[j]+p[i];d[j]=d[j]+t[i];}printf("\n");for(k=0;k<7;k++)printf(" %d",t[k]);printf("\n");for(k=0;k<7;k++)printf(" %d",p[k]);printf("\n");for(k=0;k<m;k++)printf(" %d",s[k]);printf("\n");for(k=0;k<m;k++)printf(" %d",d[k]);printf("\n");}。
java贪心算法几个经典例子1. 跳跃游戏跳跃游戏是一个非常简单的贪心算法问题,概括来说,它的目标是将一些数列中的数字与它们的下标相加,然后通过一定的规则从开始位置向后跳跃,直到跳到数组的最后一个位置。
在这个过程中,我们需要决定每一步要跳多远才能尽可能地跳到数组的最后一个位置。
具体来说,我们需要维护两个变量:一个表示目前能够跳的最远距离,另一个表示如果一步跳完所能到达的最远位置。
对于每一步,我们需要计算出在当前位置能够跳的最远距离,然后从这个范围中选出下一步的最佳位置,直到最终到达数组的结尾。
代码实现如下:```public boolean canJump(int[] nums) {int n = nums.length;int farthest = 0;for (int i = 0; i < n; i++) {if (i <= farthest) {farthest = Math.max(farthest, i + nums[i]);if (farthest >= n - 1) return true;}}return false;}```2. 最佳买卖股票时机在这个问题中,我们需要决定什么时候买入股票并在价值最高的时候卖出。
我们可以利用贪心算法来解决这个问题。
具体来说,我们需要维护两个变量:一个表示目前为止的最小股票价格,另一个表示目前为止的最大利润。
在遍历数组的过程中,我们将最小股票价格与当前价格进行比较,并尝试更新最大利润。
代码实现如下:```public int maxProfit(int[] prices) {int minPrice = Integer.MAX_VALUE;int maxProfit = 0;for (int price : prices) {if (price < minPrice) {minPrice = price;} else if (price - minPrice > maxProfit) {maxProfit = price - minPrice;}}return maxProfit;}```3. 分配饼干这个问题是关于如何将一些饼干分配给孩子们以使得他们获得最大的满足感。
java贪心算法几个经典例子
1. 零钱兑换问题
给定面额为1、5、10、25的硬币,以及一个需要兑换的金额,问最少需要多少硬币才能兑换成功。
解法:每次选择面额最大的硬币兑换,直到兑换完毕为止。
2. 分糖果问题
有m个糖果,要分给n个孩子,每个孩子至少分到一个糖果,且每个孩子分到的糖果数应尽量相近,求最小的糖果差。
解法:将m个糖果按照大小排序,依次将糖果分给n个孩子,每次将糖果分给最少的孩子。
3. 区间覆盖问题
给定多个区间,问最少需要选多少个区间才能覆盖全集。
解法:每次选择与当前未被覆盖的部分交集最大的区间添加到答案中,直到所有部分被覆盖完毕为止。
4. 任务调度问题
有n个任务需要完成,每个任务需要占用不同的时间,同时每个任务都有一个
最后期限,问如何调度任务才能最大程度地避免超时。
解法:将所有任务按照最后期限排序,依次将任务安排到最后期限之前的最近空闲时间点,尽量将任务时间安排得紧凑。