




免费预览已结束,剩余33页可下载查看
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1,第4章贪心算法,2,课程安排,3,第4章贪心算法,会场安排问题最优合并问题磁带最优存储问题磁盘文件最优存储问题程序存储问题最优服务次序问题多处最优服务次序问题d森林问题汽车加油问题区间覆盖问题硬币找钱问题删数问题数列极差问题,嵌套箱问题套汇问题信号增强装置问题磁带最大利用率问题非单位时间任务安排问题多元Huffman编码问题多元Huffman编码变形区间相交问题任务时间表问题最优分解问题可重复最优分解问题可重复最优组合分解问题旅行规划问题登山机器人问题,4,算法实现题4-1会场安排问题,问题描述:假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。)编程任务:对于给定的k个待安排的活动,编程计算使用最少会场的时间表(必须都安排完成)。,5,算法实现题4-1会场安排问题,数据输入:第一行有1个正整数k,表示有k个待安排的活动。接下来的k行中,每行有2个正整数,分别表示k个待安排的活动开始时间和结束时间。时间以0点开始的分钟计。结果输出:最少会场数。输入文件51231228253527803650输出示例3,6,算法实现题4-5程序存储问题,问题描述:设有n个程序1,2,n要存放在长度为L的磁带上。程序i存放在磁带上的长度是li,1in。程序存储问题要求确定这n个程序在磁带上的一个存储方案,使得能够在磁带上存储尽可能多的程序。编程任务:对于给定的n个程序存放在磁带上的长度,编程计算磁带上最多可以存储的程序数。,7,算法实现题4-5程序存储问题,数据输入:第一行是2个正整数,分别表示文件个数n和磁带的长度L。接下来的1行中,有n个正整数,表示程序存放在磁带上的长度。结果输出:最多可以存储的程序数。输入示例650231388020输出示例5,8,intgreedy(vectorx,intm)inti=0,sum=0,n=x.size();sort(x.begin(),x.end();while(in)sum+=xi;if(sum=m)i+;elsereturni;returnn;/所有的程序都没有磁带长,算法实现题4-5程序存储问题,贪心策略:最短程序优先排序后的数据,9,算法实现题4-6最优服务次序问题,问题描述:设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1=i=n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。编程任务:对于给定的n个顾客需要的服务时间,编程计算最优服务次序。,10,算法实现题4-6最优服务次序问题,数据输入:第一行是正整数n,表示有n个顾客。接下来的1行中,有n个正整数,表示n个顾客需要的服务时间。结果输出:计算出的最小平均等待时间。输入示例1056121991000234335599812输出示例532.00,11,算法实现题4-6最优服务次序问题,doublegreedy(vectorx)inti,n=x.size();sort(x.begin(),x.end();for(i=1;in;+i)xi+=xi-1;doublet=0;for(i=0;in;+i)t+=xi;t/=n;returnt;,定义:vectorx;读取数据:intn;scanf(“%d”,12,算法实现题4-7多处最优服务次序问题,问题描述:设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1=i=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。编程任务:对于给定的n个顾客需要的服务时间和s的值,编程计算最优服务次序。,13,算法实现题4-7多处最优服务次序问题,数据输入:第一行有2个正整数n和s,表示有n个顾客且有s处可以提供顾客需要的服务。接下来的1行中,有n个正整数,表示n个顾客需要的服务时间。结果输出:最小平均等待时间。输入示例10256121991000234335599812输出示例336,14,算法实现题4-7多处最优服务次序问题,doublegreed(vectorx,ints)vectorst(s+1,0);vectorsu(s+1,0);intn=x.size();sort(x.begin(),x.end();inti=0,j=0;while(i0)/寻找最近下降点inti;for(i=0;(i1/删除前导0,能使用m吗?,25,算法实现题4-15套汇问题,问题描述:套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如,假定1美元可以买0.7英镑,1英镑可以买9.5法郎,且1法郎可以买到0.16美元。通过货币兑换,一个商人可以从1美元开始买入,得到0.79.50.16=1.064美元,从而获得6.4%的利润。编程任务:给定n种货币c1,c2,c3,.,cn的有关兑换率,试设计一个有效算法,用以确定是否存在套汇的可能性。,26,输入示例3USDollarBritishPoundFrenchFranc3USDollar0.5BritishPoundBritishPound10.0FrenchFrancFrenchFranc0.21USDollar0输出示例Case1yes,算法实现题4-15套汇问题,数据输入:本题有多个测试数据项。每个测试数据项的第一行中只有1个整数n(1n30),表示货币总数。其后n行给出n种货币的名称。接下来的一行中有1个整数m,表示有m种不同的货币兑换率。其后m行给出m种不同的货币兑换率,每行有3个数据项ci,rij和cj,表示货币ci和cj的兑换率为rij。文件最后以数字0结束。结果输出:对每个测试数据项j,如果存在套汇的可能性则输出“Casejyes”,否则输出“Casejno”。,27,算法实现题4-15套汇问题,while(1)cinn;if(n=0)break;/输入结束for(i=0;inamei;/读取货币名称for(i=0;iedges;/兑换率数目for(i=0;iaxb;for(j=0;strcmp(a,namej);j+);/确定a的下标for(k=0;strcmp(b,namek);k+);/确定b的下标rjk=x;,28,算法实现题4-15套汇问题,while(1)for(i=0;i1.0)break;/搜索赢利情况if(in)coutcase(cases)yesendl;elsecoutcase(cases)non;intervalinte100;for(inti=0;iab;if(ab)swap(a,b);intei.start=a;intei.end=b;sort(inte,inte+n,cmp);coutn-GreedySelector(n,inte)endl;,33,算法实现题4-21区间相交问题,贪心选择:intGreedySelector(intn,intervalinte)intcount=1;intj=0;/区间的起点for(inti=1;iintej.end)count+;j=i;returncount;,34,算法实现题4-23最优分解问题,问题描述:设n是一个正整数。现在要求将n分解为若干个互不相同的自然数的和,且使这些自然数的乘积最大。编程任务:对于给定的正整数n,编程计算最优分解方案。数据输入:第1行是正整数n。结果输出:计算出的最大乘积。输入示例10输出示例30,35,算法实现题4-23最优分解问题,voiddicomp()k=1;if(nak)k+;ak=ak-1+1;n-=ak;if(n=ak)ak+;-n;for(inti=0;in;+i)ak-i+;,大数运算,36,算法实现题4-24可重复最优分解问题,问题描述:设n是一个正整数。现在要求将n分解为若干个自然数的和,且使这些自然数的乘积最大。编程任务:对于给定的正整数n,编程计算最优分解方案。数据输入:文件的第1行是正整数n。结果输出:计算出的最大乘积。输入示例10输出示例36,37,算法实现题4-24可重复最优分解问题,若a+b=const,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论