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

1、1,第4章 贪心算法,2,课程安排,3,第4章 贪心算法,会场安排问题 最优合并问题 磁带最优存储问题 磁盘文件最优存储问题 程序存储问题 最优服务次序问题 多处最优服务次序问题 d森林问题 汽车加油问题 区间覆盖问题 硬币找钱问题 删数问题 数列极差问题,嵌套箱问题 套汇问题 信号增强装置问题 磁带最大利用率问题 非单位时间任务安排问题 多元Huffman编码问题 多元Huffman编码变形 区间相交问题 任务时间表问题 最优分解问题 可重复最优分解问题 可重复最优组合分解问题 旅行规划问题 登山机器人问题,4,算法实现题4-1 会场安排问题,问题描述： 假设要在足够多的会场里安排一批活动，

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

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

4、输出示例 5,8,int 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; return n;/所有的程序都没有磁带长 ,算法实现题4-5 程序存储问题,贪心策略：最短程序优先 排序后的数据,9,算法实现题4-6 最优服务次序问题,问题描述： 设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti, 1=i = n 。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时

5、间是n 个顾客等待服务时间的总和除以n。 编程任务： 对于给定的n个顾客需要的服务时间，编程计算最优服务次序。,10,算法实现题4-6 最优服务次序问题,数据输入： 第一行是正整数n，表示有n 个顾客。接下来的1行中，有n个正整数，表示n个顾客需要的服务时间。 结果输出: 计算出的最小平均等待时间。 输入示例 10 56 12 1 99 1000 234 33 55 99 812 输出示例 532.00,11,算法实现题4-6 最优服务次序问题,double greedy( vector x) int i,n=x.size(); sort(x.begin(),x.end(); for(i=1;

6、in;+i) xi += xi-1; double t=0; for(i=0;in;+i) t+=xi; t /= n; return t; ,定义： vector x; 读取数据： int n; scanf(“%d”, ,12,算法实现题4-7 多处最优服务次序问题,问题描述： 设有n 个顾客同时等待一项服务。顾客i需要的服务时间为ti ,1= i = n。共有s 处可以提供此项服务。应如何安排n 个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。 编程任务： 对于给定的n个顾客需要的服务时间和s的值，编程计算最优服务次序。,13,算法实现题4-7

7、多处最优服务次序问题,数据输入： 第一行有2 个正整数n 和s，表示有n 个顾客且有s 处可以提供顾客需要的服务。接下来的1 行中，有n个正整数，表示n个顾客需要的服务时间。 结果输出: 最小平均等待时间。 输入示例 10 2 56 12 1 99 1000 234 33 55 99 812 输出示例 336,14,算法实现题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; w

8、hile(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; ,排序后的数据,15,算法实现题4-9 汽车加油问题,问题描述 一辆汽车加满油后可行驶nkm 。旅途中有若干个加油站。设计一个有效算法，指出应在哪些加油站停靠加油，使沿途加油次数最少。 编程任务 对于给定的n和k个加油站位置，编程计算最少加油次数。,16,算法实现题4-9 汽车加油问题,数据输入 第1行有2个正整数n和k，表示汽车加满油后可行驶nkm，且旅途有k个加油站。接下来

9、的一行中，有k+1个整数，表示第k个加油站与第k-1个加油站之间的距离。第0个加油站表示出发地，汽车已加满油。第k+1个加油站表示目的地。 结果输出 计算出的最少加油次数。如果无法到达目的地，则输出”No Solution”。,输入示例 7 7 1 2 3 4 5 1 6 6,输出示例 4,17,算法实现题4-9 汽车加油问题,int greedy(vector x,int n) int j,i,s,sum=0, k=x.size(); for(j=0;j n) cout n) sum+,s = xi; return sum; ,i=3 10 i=4 9 i=6 12 i=7 12,18,算法

10、实现题4-9 汽车加油问题,读取数据： int t,n,k; scanf(%d%d,19,算法实现题4-10 区间覆盖问题,问题描述： 设x1 , x2 ,. , xn 是实直线上的n个点。用固定长度的闭区间覆盖这n个点，至少需要多少个这样的固定长度闭区间?设计解此问题的有效算法。 编程任务： 对于给定的实直线上的n个点和闭区间的长度k，编程计算覆盖点集的最少区间数。,20,算法实现题4-10 区间覆盖问题,数据输入： 第一行有2 个正整数n和k，表示有n个点，且固定长度闭区间的长度为k。接下来的1 行中，有n个整数，表示n个点在实直线上的坐标（可能相同）。 结果输出: 最少区间数。 输入示例

11、 7 3 1 2 3 4 5 -2 6 输出文件示例 3,21,算法实现题4-10 区间覆盖问题,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; ,22,算法实现题4-12 删数问题,问题描述： 给定n 位正整数a，去掉其中任意kn 个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a 和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。

12、 编程任务： 对于给定的正整数a，编程计算删去k个数字后得到的最小数。,23,算法实现题4-12 删数问题,数据输入： 文件的第1 行是1 个正整数a。第2 行是正整数k。 结果输出: 计算出的最小数。 输入示例 178543 4 输出文件示例 13,24,算法实现题4-12 删数问题,void delek(string a, int k)/在整数a中删除k个数字 int m = a.size(); if(k = m) a.erase();return;/全部删除 while(k 0) /寻找最近下降点 int i; for(i=0;(i 1 /删除前导0,能使用m吗？,25,算法实现题4-1

13、5 套汇问题,问题描述： 套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。 例如，假定1 美元可以买0.7 英镑，1 英镑可以买9.5 法郎，且1 法郎可以买到0.16美元。 通过货币兑换，一个商人可以从1 美元开始买入，得到0.79.50.16=1.064美元，从而获得6.4%的利润。 编程任务： 给定n 种货币c1,c2,c3,.,cn的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。,26,输入示例 3 USDollar BritishPound FrenchFranc 3 USDollar 0.5 BritishPound BritishPo

14、und 10.0 FrenchFranc FrenchFranc 0.21 USDollar 0 输出示例 Case 1 yes,算法实现题4-15 套汇问题,数据输入： 本题有多个测试数据项。每个测试数据项的第一行中只有1 个整数n (1n 30)，表示货币总数。其后n行给出n种货币的名称。接下来的一行中有1 个整数m，表示有m种不同的货币兑换率。其后m行给出m种不同的货币兑换率，每行有3 个数据项ci ， rij 和cj ，表示货币ci 和cj的兑换率为 rij。文件最后以数字0 结束。 结果输出: 对每个测试数据项j，如果存在套汇的可能性则输出“Case j yes”， 否则输出“Cas

15、e j no”。,27,算法实现题4-15 套汇问题,while(1) cin n; if(n = 0) break;/输入结束 for(i=0; i namei;/读取货币名称 for(i=0; i 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; ,28,算法实现题4-15 套汇问题,while(1) for(i=0; i 1.0) break;/搜索赢利情况 if(i n) cout case (cases)

16、 yesendl; else coutcase (cases) noendl; ,只要搜到一个赢利就行,29,算法实现题4-15 套汇问题,3 USDollar BritishPound FrenchFranc 6 USDollar 0.5 BritishPound USDollar 4.9 FrenchFranc BritishPound 10.0 FrenchFranc BritishPound 1.99 USDollar FrenchFranc 0.09 BritishPound FrenchFranc 0.19 USDollar Answer: no,30,算法实现题4-21 区间相交

17、问题,问题描述： 给定x 轴上n 个闭区间。去掉尽可能少的闭区间，使剩下的闭区间都不相交。 编程任务： 给定n 个闭区间，编程计算去掉的最少闭区间数。 数据输入： 第一行是正整数n，表示闭区间数。接下来的n行中，每行有2 个整数，分别表示闭区间的2个端点。 结果输出: 计算出的去掉的最少闭区间数。,输入示例 3 10 20 10 15 20 15 输出文件示例 2 /与活动安排类似 if (ab) swap(a, b); 按右端点从小到大排序; 依左端点超过右端点进行选择.,31,算法实现题4-21 区间相交问题,数据结构： struct interval int start; int end

18、; ; 比较函数： bool cmp(interval a, interval b) if (a.endb.end) return true; else return false; ,32,算法实现题4-21 区间相交问题,在int main() 中： int n; int a,b; cinn; interval 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;,33,算法实现题4-21 区间相交问题,贪心选择： int GreedySelector(int n, interval inte ) int count = 1; int j=0;/区间的起点 for (int i=1; iintej.end) count+; j=i; return count; ,34,算法实现题4-23 最优分解问题,问题描述： 设n是一个正整数。现在要求将n分解为若干个互不相同的自然数的和，且使这些自然数的乘