第4章-贪心算法-习题.ppt

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,