第4章贪心算法习题(阅读)课件.ppt

1、12课程安排课程安排12345678910111213141516周二周二P PP PTTTTP PTTTTP PTTTTP PTTTTTTTTP P周四周四P PP PP PP PP PP PP PP PP PP PP PP PP PP P 端午端午考试考试TT3第第4章章 贪心算法贪心算法会场安排问题会场安排问题最优合并问题最优合并问题磁带最优存储问题磁带最优存储问题磁盘文件最优存储问题磁盘文件最优存储问题程序存储问题程序存储问题最优服务次序问题最优服务次序问题多处最优服务次序问题多处最优服务次序问题d森林问题森林问题汽车加油问题汽车加油问题 区间覆盖问题区间覆盖问题 硬币找钱问题硬币找钱

2、问题 删数问题删数问题 数列极差问题数列极差问题嵌套箱问题嵌套箱问题 套汇问题套汇问题 信号增强装置问题信号增强装置问题 磁带最大利用率问题磁带最大利用率问题 非单位时间任务安排问题非单位时间任务安排问题 多元多元Huffman编码问题编码问题 多元多元Huffman编码变形编码变形 区间相交问题区间相交问题 任务时间表问题任务时间表问题 最优分解问题最优分解问题 可重复最优分解问题可重复最优分解问题 可重复最优组合分解问题可重复最优组合分解问题 旅行规划问题旅行规划问题 登山机器人问题登山机器人问题4算法实现题算法实现题4-1 会场安排问题会场安排问题 问题描述：问题描述：假设要在足够多的会

3、场里安排一批活动，并希望使假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安用尽可能少的会场。设计一个有效的贪心算法进行安排。排。(这个问题实际上是著名的图着色问题。若将每一这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。的最小会场数。)编程任务：编程任务：对于给定的对于给定的k个待安排的活动，编程计算使用最少个待安排的活动，编程计算使用最少会场的时间表会场的时间表

4、(必须都安排完成必须都安排完成)。5算法实现题算法实现题4-1 会场安排问题会场安排问题 数据输入：数据输入：第一行有第一行有1 个正整数个正整数k，表示有，表示有k个待安排的活动。接个待安排的活动。接下来的下来的k行中，每行有行中，每行有2个正整数，分别表示个正整数，分别表示k个待安排个待安排的活动开始时间和结束时间。时间以的活动开始时间和结束时间。时间以0 点开始的分钟计。点开始的分钟计。结果输出结果输出:最少会场数。最少会场数。输入文件输入文件51 2312 2825 3527 8036 50输出示例输出示例36算法实现题算法实现题4-5 程序存储问题程序存储问题问题描述：问题描述：设有

5、设有n 个程序个程序1,2,n 要存放在长度为要存放在长度为L的磁带上。的磁带上。程序程序i存放在磁带上的长度是存放在磁带上的长度是 li，1 i n。程序存储问题要求确定这程序存储问题要求确定这n 个程序在磁带上的一个个程序在磁带上的一个存储方案，使得能够在磁带上存储尽可能多的程序。存储方案，使得能够在磁带上存储尽可能多的程序。编程任务：编程任务：对于给定的对于给定的n个程序存放在磁带上的长度，编程计个程序存放在磁带上的长度，编程计算磁带上最多可以存储的程序数。算磁带上最多可以存储的程序数。7算法实现题算法实现题4-5 程序存储问题程序存储问题数据输入：数据输入：第一行是第一行是2 个正整数

6、，分别表示文件个数个正整数，分别表示文件个数n和磁带的长和磁带的长度度L。接下来的。接下来的1 行中，有行中，有n个正整数，表示程序存放在磁个正整数，表示程序存放在磁带上的长度。带上的长度。结果输出结果输出:最多可以存储的程序数。最多可以存储的程序数。输入示例输入示例6 502 3 13 8 80 20输出示例输出示例5i012345x2313880208int greedy(vector x,int m)int i=0,sum=0,n=x.size();sort(x.begin(),x.end();while(i n)sum+=xi;if(sum=m)i+;else return i;ret

7、urn n;/所有的程序都没有磁带长所有的程序都没有磁带长算法实现题算法实现题4-5 程序存储问题程序存储问题i012345x238132080贪心策略：最短程序优先贪心策略：最短程序优先排序后的数据排序后的数据9算法实现题算法实现题4-6 最优服务次序问题最优服务次序问题 问题描述：问题描述：设有设有n 个顾客同时等待一项服务。顾客个顾客同时等待一项服务。顾客i需要的服务需要的服务时间为时间为ti,1=i=n。应如何安排。应如何安排n个顾客的服务次序个顾客的服务次序才能使平均等待时间达到最小才能使平均等待时间达到最小?平均等待时间是平均等待时间是n 个个顾客等待服务时间的总和除以顾客等待服务

8、时间的总和除以n。编程任务：编程任务：对于给定的对于给定的n个顾客需要的服务时间，编程计算最个顾客需要的服务时间，编程计算最优服务次序。优服务次序。10算法实现题算法实现题4-6 最优服务次序问题最优服务次序问题数据输入：数据输入：第一行是正整数第一行是正整数n，表示有，表示有n 个顾客。接下来的个顾客。接下来的1行行中，有中，有n个正整数，表示个正整数，表示n个顾客需要的服务时间。个顾客需要的服务时间。结果输出结果输出:计算出的最小平均等待时间。计算出的最小平均等待时间。输入示例输入示例1056 12 1 99 1000 234 33 55 99 812输出示例输出示例532.0011算法实

9、现题算法实现题4-6 最优服务次序问题最优服务次序问题double greedy(vector x)int i,n=x.size();sort(x.begin(),x.end();for(i=1;in;+i)xi+=xi-1;double t=0;for(i=0;in;+i)t+=xi;t/=n;return t;i0123456789x1123355569999 2348121000加加11346 101 157 256 355 589 1401 2401定义：定义：vector x;读取数据：读取数据：int n;scanf(“%d”,&n);int temp;for(int i=0;in

10、;i+)scanf(“%d”,&temp);x.push_back(temp);12算法实现题算法实现题4-7 多处最优服务次序问题多处最优服务次序问题 问题描述：问题描述：设有设有n 个顾客同时等待一项服务。顾客个顾客同时等待一项服务。顾客i需要的服务需要的服务时间为时间为ti,1=i=n。共有。共有s 处可以提供此项服务。处可以提供此项服务。应如何安排应如何安排n 个顾客的服务次序才能使平均等待时间个顾客的服务次序才能使平均等待时间达到最小达到最小?平均等待时间是平均等待时间是n个顾客等待服务时间的总个顾客等待服务时间的总和除以和除以n。编程任务：编程任务：对于给定的对于给定的n个顾客需要

11、的服务时间和个顾客需要的服务时间和s的值，编程的值，编程计算最优服务次序。计算最优服务次序。13算法实现题算法实现题4-7 多处最优服务次序问题多处最优服务次序问题数据输入：数据输入：第一行有第一行有2 个正整数个正整数n 和和s，表示有，表示有n 个顾客且有个顾客且有s 处可以提供顾客需要的服务。接下来的处可以提供顾客需要的服务。接下来的1 行中，有行中，有n个正整数，表示个正整数，表示n个顾客需要的服务时间。个顾客需要的服务时间。结果输出结果输出:最小平均等待时间。最小平均等待时间。输入示例输入示例10 256 12 1 99 1000 234 33 55 99 812输出示例输出示例33

12、614算法实现题算法实现题4-7 多处最优服务次序问题多处最优服务次序问题double greed(vector x,int s)vector st(s+1,0);vector su(s+1,0);int n=x.size();sort(x.begin(),x.end();int i=0,j=0;while(i n)stj+=xi;suj+=stj;+i,+j;if(j=s)j=0;double t=0;for(i=0;is;+i)t+=sui;t/=n;return t;i0123456789x112 33 55 56 99 99 234 812 1000排序后的数据排序后的数据st服务数组

13、服务数组01112su求和数组求和数组0111215算法实现题算法实现题4-9 汽车加油问题汽车加油问题问题描述问题描述一辆汽车加满油后可行驶一辆汽车加满油后可行驶nkm。旅途中有若干个加。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。加油，使沿途加油次数最少。编程任务编程任务对于给定的对于给定的n和和k个加油站位置，编程计算最少加油个加油站位置，编程计算最少加油次数。次数。16算法实现题算法实现题4-9 汽车加油问题汽车加油问题数据输入数据输入第第1行有行有2个正整数个正整数n和和k，表示汽车加满油后可行

14、驶，表示汽车加满油后可行驶nkm，且旅途有且旅途有k个加油站。接下来的一行中，有个加油站。接下来的一行中，有k+1个整数，表示个整数，表示第第k个加油站与第个加油站与第k-1个加油站之间的距离。第个加油站之间的距离。第0个加油站表个加油站表示出发地，汽车已加满油。第示出发地，汽车已加满油。第k+1个加油站表示目的地。个加油站表示目的地。结果输出结果输出计算出的最少加油次数。如果无法到达目的地，则输计算出的最少加油次数。如果无法到达目的地，则输出出”No Solution”。输入示例输入示例7 7 1 2 3 4 5 1 6 6输出示例输出示例 4起点起点终点终点加油站数加油站数0 1 2 3

15、4 5 6 7 81 2 3 4 5 1 6 6x17算法实现题算法实现题4-9 汽车加油问题汽车加油问题int greedy(vector x,int n)int j,i,s,sum=0,k=x.size();for(j=0;j n)coutNo Soultionendl;return-1;for(i=0,s=0;i n)sum+,s=xi;return sum;k01234567x12345166i=3 10i=4 9i=6 12i=7 12起点起点终点终点加油站数加油站数0 1 2 3 4 5 6 7 81 2 3 4 5 1 6 6x18算法实现题算法实现题4-9 汽车加油问题汽车加油

16、问题读取数据：读取数据：int t,n,k;scanf(%d%d,&n,&k);vector x;for(int i=0;i=0)printf(%dn,temp);19算法实现题算法实现题4-10 区间覆盖问题区间覆盖问题 问题描述：问题描述：设设x1,x2,.,xn 是实直线上的是实直线上的n个点。用固定长度个点。用固定长度的闭区间覆盖这的闭区间覆盖这n个点，至少需要多少个这样的固定个点，至少需要多少个这样的固定长度闭区间长度闭区间?设计解此问题的有效算法。设计解此问题的有效算法。编程任务：编程任务：对于给定的实直线上的对于给定的实直线上的n个点和闭区间的长度个点和闭区间的长度k，编，编程计

17、算覆盖点集的最少区间数。程计算覆盖点集的最少区间数。20算法实现题算法实现题4-10 区间覆盖问题区间覆盖问题数据输入：数据输入：第一行有第一行有2 个正整数个正整数n和和k，表示有，表示有n个点，且固定个点，且固定长度闭区间的长度为长度闭区间的长度为k。接下来的。接下来的1 行中，有行中，有n个整数，个整数，表示表示n个点在实直线上的坐标（可能相同）。个点在实直线上的坐标（可能相同）。结果输出结果输出:最少区间数。最少区间数。输入示例输入示例7 31 2 3 4 5-2 6输出文件示例输出文件示例30123456-2-1012345621算法实现题算法实现题4-10 区间覆盖问题区间覆盖问题

18、int greedy(vector x,int k)int i,sum=1,n=x.size();sort(x.begin(),x.end();int temp=x0;/区间的起始位置区间的起始位置for(i=1;i k)sum+,temp=xi;return sum;0123456-2-1012345622算法实现题算法实现题4-12 删数问题删数问题 问题描述：问题描述：给定给定n 位正整数位正整数a，去掉其中任意，去掉其中任意kn 个数字后，剩下个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的的数字按原次序排列组成一个新的正整数。对于给定的n位正整数位正整数a 和正整数和正

19、整数k，设计一个算法找出剩下数字组成，设计一个算法找出剩下数字组成的新数最小的删数方案。的新数最小的删数方案。编程任务：编程任务：对于给定的正整数对于给定的正整数a，编程计算删去，编程计算删去k个数字后得到的个数字后得到的最小数。最小数。23算法实现题算法实现题4-12 删数问题删数问题 数据输入：数据输入：文件的第文件的第1 行是行是1 个正整数个正整数a。第。第2 行是正整数行是正整数k。结果输出结果输出:计算出的最小数。计算出的最小数。输入示例输入示例1785434输出文件示例输出文件示例1324算法实现题算法实现题4-12 删数问题删数问题void delek(string a,int

20、 k)/在整数在整数a中删除中删除k个数字个数字int m=a.size();if(k=m)a.erase();return;/全部删除全部删除while(k 0)/寻找最近下降点寻找最近下降点int i;for(i=0;(i a.size()-1)&(ai 1&a0=0)a.erase(0,1);/删除前导删除前导0能使用能使用m吗？吗？25算法实现题算法实现题4-15 套汇问题套汇问题问题描述：问题描述：套汇是指利用货币汇兑率的差异将一个单位的某种套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。货币转换为大于一个单位的同种货币。例如，假定例如，假定1 美元可以

21、买美元可以买0.7 英镑，英镑，1 英镑可以买英镑可以买9.5 法郎，法郎，且且1 法郎可以买到法郎可以买到0.16美元。美元。通过货币兑换，一个商人可以从通过货币兑换，一个商人可以从1 美元开始买入，得到美元开始买入，得到0.79.50.16=1.064美元，从而获得美元，从而获得6.4%的利润。的利润。编程任务：编程任务：给定给定n 种货币种货币c1,c2,c3,.,cn的有关兑换率，试设计一的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。个有效算法，用以确定是否存在套汇的可能性。26输入示例输入示例3USDollarBritishPoundFrenchFranc3USDo

22、llar 0.5 BritishPoundBritishPound 10.0 FrenchFrancFrenchFranc 0.21 USDollar0输出示例输出示例Case 1 yes算法实现题算法实现题4-15 套汇问题套汇问题数据输入：数据输入：本题有多个测试数据项。每个测本题有多个测试数据项。每个测试数据项的第一行中只有试数据项的第一行中只有1 个整数个整数n(1n 30)，表示货币总数。其后，表示货币总数。其后n行给出行给出n种货币的名称。接下来种货币的名称。接下来的一行中有的一行中有1 个整数个整数m，表示有，表示有m种不同的货币兑换率。其后种不同的货币兑换率。其后m行给行给出出

23、m种不同的货币兑换率，每行有种不同的货币兑换率，每行有3 个数据项个数据项ci，rij 和和cj，表示货币，表示货币ci 和和cj的兑换率为的兑换率为 rij。文件最后以。文件最后以数字数字0 结束。结束。结果输出结果输出:对每个测试数据项对每个测试数据项j，如果存在套，如果存在套汇的可能性则输出汇的可能性则输出“Case j yes”，否则输出否则输出“Case j no”。27算法实现题算法实现题4-15 套汇问题套汇问题while(1)cin n;if(n=0)break;/输入结束输入结束for(i=0;i namei;/读取货币名称读取货币名称for(i=0;i n;+i)for(j

24、=0;j edges;/兑换率数目兑换率数目for(i=0;i a x b;for(j=0;strcmp(a,namej);+j);/确定确定a的下标的下标for(k=0;strcmp(b,namek);+k);/确定确定b的下标的下标rjk=x;01200.000.500.0010.000.0010.0020.210.000.0028算法实现题算法实现题4-15 套汇问题套汇问题while(1)for(i=0;i n;+i)rii=max(1.0,rii);/自身至少为自身至少为1for(k=0;k n;+k)/Floyd算法算法for(i=0;i n;+i)for(j=0;j n;+j)r

25、ij=max(rij,rik*rkj);for(i=0;i 1.0)break;/搜索赢利情况搜索赢利情况if(i n)cout case(cases)yesendl;else coutcase(cases)nob)swap(a,b);按右端点从小到大排按右端点从小到大排序序;1.依左端点超过右端点依左端点超过右端点进行选择进行选择.31算法实现题算法实现题4-21 区间相交问题区间相交问题数据结构：数据结构：struct intervalint start;int end;比较函数：比较函数：bool cmp(interval a,interval b)if(a.endn;interval

26、inte100;for(int i=0;iab;if(ab)swap(a,b);intei.start=a;intei.end=b;sort(inte,inte+n,cmp);coutn-GreedySelector(n,inte)endl;start152076707099 1019end100621087100 99 100 102 1833算法实现题算法实现题4-21 区间相交问题区间相交问题贪心选择：贪心选择：int GreedySelector(int n,interval inte)int count=1;int j=0;/区间的起点区间的起点for(int i=1;iintej.

27、end)count+;j=i;return count;start5679701709910120end6781899100 100 100 102 21034算法实现题算法实现题4-23 最优分解问题最优分解问题问题描述：问题描述：设设n是一个正整数。现在要求将是一个正整数。现在要求将n分解为若干个分解为若干个互不互不相同的相同的自然数的和，且使这些自然数的乘积最大。自然数的和，且使这些自然数的乘积最大。编程任务：编程任务：对于给定的正整数对于给定的正整数n，编程计算最优分解方案。，编程计算最优分解方案。数据输入：数据输入：第第1 行是正整数行是正整数n。结果输出结果输出:计算出的最大乘积。

28、计算出的最大乘积。输入示例输入示例10 输出示例输出示例3035算法实现题算法实现题4-23 最优分解问题最优分解问题void dicomp()k=1;if(n 3)a1=0;return;/n=1,2if(n ak)k+;ak=ak-1+1;n-=ak;if(n=ak)ak+;-n;for(int i=0;i n;+i)ak-i+;下标下标0123n10851a2345大数运算大数运算36算法实现题算法实现题4-24 可重复最优分解问题可重复最优分解问题问题描述：问题描述：设设n是一个正整数。现在要求将是一个正整数。现在要求将n分解为若干个自然分解为若干个自然数的和，且使这些自然数的乘积最大

29、。数的和，且使这些自然数的乘积最大。编程任务：编程任务：对于给定的正整数对于给定的正整数n，编程计算最优分解方案。，编程计算最优分解方案。数据输入：数据输入：文件的第文件的第1 行是正整数行是正整数n。结果输出结果输出:计算出的最大乘积。计算出的最大乘积。输入示例输入示例10输出示例输出示例3637算法实现题算法实现题4-24 可重复最优分解问题可重复最优分解问题若若a+b=const,则则|a-b|越小，越小，ab越大。越大。贪心策略：贪心策略：)3mod(2 32)3mod(1 34)3mod(0 3max11 3/)2(3/)4(3/11 n n nmmm，mnnnnkiijikii则38算法实现题算法实现题4-24 可重复最优分解问题可重复最优分解问题void compute(int n)int r=n%3;t1=1;int k=n/3;length=1;/大数的长度大数的长度,是全局变量是全局变量if(r=1)t1=4;k=(n-4)/3;if(r=2)t1=2;k=(n-2)/3;for(int i=1;i 0;-i)cout ti;coutendl;)3mod(2 32)3mod(1 34)3mod(0 3max 3/)2(3/)4(3/1 n n nmnnnkii