贪心算法习题课件.ppt

《贪心算法习题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章贪心算法1课程安排12345678910111213141516周二PPTTPTTPTTPTTTTP周四PPPPPPPPPPPPPP端午考试T2第4章贪心算法会场安排问题最优合并问题磁带最优存储问题磁盘文件最优存储问题程序存储问题最优服务次序问题多处最优服务次序问题d森林问题汽车加油问题区间覆盖问题硬币找钱问题删数问题数列极差问题嵌套箱问题套汇问题信号增强装置问题磁带最大利用率问题非单位时间任务安排问题多元Huffman编码问题多元Huffman编码变形区间相交问题任务时间表问题最优分解问题可重复最优分解问题可重复最优组合分解问题旅行规划问题登山机器人问题3算法实现题4-1会场安排问

2、题问题描述：假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。)编程任务：对于给定的k个待安排的活动，编程计算使用最少会场的时间表(必须都安排完成)。4算法实现题4-1会场安排问题数据输入：第一行有1个正整数k，表示有k个待安排的活动。接下来的k行中，每行有2个正整数，分别表示k个待安排的活动开始时间和结束时间。时间以0点开始的分钟计。结果输出:最少会场数。输入文件51231228253527803

3、650输出示例35算法实现题4-5程序存储问题问题描述：设有n个程序{1,2,…,n}要存放在长度为L的磁带上。程序i存放在磁带上的长度是li，1≤i≤n。程序存储问题要求确定这n个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。编程任务：对于给定的n个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。6算法实现题4-5程序存储问题数据输入：第一行是2个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。结果输出:最多可以存储的程序数。输入示例650231388020输出示例5i012345x2313880207in

4、tgreedy(vectorx,intm){inti=0,sum=0,n=x.size();sort(x.begin(),x.end());while(i

5、总和除以n。编程任务：对于给定的n个顾客需要的服务时间，编程计算最优服务次序。9算法实现题4-6最优服务次序问题数据输入：第一行是正整数n，表示有n个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。结果输出:计算出的最小平均等待时间。输入示例1056121991000234335599812输出示例532.0010算法实现题4-6最优服务次序问题doublegreedy(vectorx){inti,n=x.size();sort(x.begin(),x.end());for(i=1;i

6、n;++i)t+=x[i];t/=n;returnt;}i0123456789x11233555699992348121000加1134610115725635558914012401定义：vectorx;读取数据：intn;scanf(“%d”,&n);inttemp;for(inti=0;i

7、最小?平均等待时间是n个顾客等待服务时间的总和除以n。编程任务：对于给定的n个顾客需要的服务时间和s的值，编程计算最优服务次序。12算法实现题4-7多处最优服务次序问题数据输入：第一行有2个正整数n和s，表示有n个顾客且有s处可以提供顾客需要的服务。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。结果输出:最小平均等待时间。输入示例10256121991000234335599812输出示例33613算法实现题