《第4章-贪心算法-习题ppt课件》由会员分享，可在线阅读，更多相关《第4章-贪心算法-习题ppt课件（38页珍藏版）》请在金锄头文库上搜索。
1、 1 第4章贪心算法 2 课程安排 3 第4章贪心算法 会场安排问题最优合并问题磁带最优存储问题磁盘文件最优存储问题程序存储问题最优服务次序问题多处最优服务次序问题d森林问题汽车加油问题区间覆盖问题硬币找钱问题删数问题数列极差问题 嵌套箱问题套汇问题信号增强装置问题磁带最大利用率问题非单位时间任务安排问题多元Huffman编码问题多元Huffman编码变形区间相交问题任务时间表问题最优分解问题可重复最优分解问题可重复最优组合分解问题旅行规划问题登山机器人问题 4 算法实现题4 1会场安排问题 问题描述 假设要在足够多的会场里安排一批活动 并希望使用尽可能少的会场 设计一个有效的贪心算法进行安排
2、 这个问题实际上是著名的图着色问题 若将每一个活动作为图的一个顶点 不相容活动间用边相连 使相邻顶点着有不同颜色的最小着色数 相应于要找的最小会场数 编程任务 对于给定的k个待安排的活动 编程计算使用最少会场的时间表 必须都安排完成 5 算法实现题4 1会场安排问题 数据输入 第一行有1个正整数k 表示有k个待安排的活动 接下来的k行中 每行有2个正整数 分别表示k个待安排的活动开始时间和结束时间 时间以0点开始的分钟计 结果输出 最少会场数 输入文件51231228253527803650输出示例3 6 算法实现题4 5程序存储问题 问题描述 设有n个程序 1 2 n 要存放在长度为L的磁带
3、上 程序i存放在磁带上的长度是li 1 i n 程序存储问题要求确定这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 i
4、 n sum x i 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个顾客需要的服务时
5、间 结果输出 计算出的最小平均等待时间 输入示例1056121991000234335599812输出示例532 00 11 算法实现题4 6最优服务次序问题 doublegreedy vectorx inti n x size sort x begin x end for i 1 i n i x i x i 1 doublet 0 for i 0 i n i t x i t n returnt 定义 vectorx 读取数据 intn scanf d 12 算法实现题4 7多处最优服务次序问题 问题描述 设有n个顾客同时等待一项服务 顾客i需要的服务时间为ti 1 i n 共有s处可以提供此
6、项服务 应如何安排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 v
7、ectorsu s 1 0 intn x size sort x begin x end inti 0 j 0 while i n st j x i su j st j i j if j s j 0 doublet 0 for i 0 i s i t su i t n returnt 排序后的数据 15 算法实现题4 9汽车加油问题 问题描述一辆汽车加满油后可行驶nkm 旅途中有若干个加油站 设计一个有效算法 指出应在哪些加油站停靠加油 使沿途加油次数最少 编程任务对于给定的n和k个加油站位置 编程计算最少加油次数 16 算法实现题4 9汽车加油问题 数据输入第1行有2个正整数n和k 表示汽车
8、加满油后可行驶nkm 且旅途有k个加油站 接下来的一行中 有k 1个整数 表示第k个加油站与第k 1个加油站之间的距离 第0个加油站表示出发地 汽车已加满油 第k 1个加油站表示目的地 结果输出计算出的最少加油次数 如果无法到达目的地 则输出 NoSolution 输入示例7712345166 输出示例4 17 算法实现题4 9汽车加油问题 intgreedy vectorx intn intj i s sum 0 k x size for j 0 jn coutn sum s x i returnsum i 310i 49i 612i 712 18 算法实现题4 9汽车加油问题 读取数据 i
9、ntt 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个点在实直线上的坐标 可能相同 结果输出 最少区间数 输入示例7312345 26输出文件示例3 21 算法实现题4 10区间覆盖问题 intgreed
10、y vectorx intk inti sum 1 n x size sort x begin x end inttemp x 0 区间的起始位置for i 1 ik sum temp x i returnsum 22 算法实现题4 12删数问题 问题描述 给定n位正整数a 去掉其中任意k n个数字后 剩下的数字按原次序排列组成一个新的正整数 对于给定的n位正整数a和正整数k 设计一个算法找出剩下数字组成的新数最小的删数方案 编程任务 对于给定的正整数a 编程计算删去k个数字后得到的最小数 23 算法实现题4 12删数问题 数据输入 文件的第1行是1个正整数a 第2行是正整数k 结果输出 计算
11、出的最小数 输入示例1785434输出文件示例13 24 算法实现题4 12删数问题 voiddelek stringa intk 在整数a中删除k个数字intm a size if k m a erase return 全部删除while k 0 寻找最近下降点inti for i 0 i1 删除前导0 能使用m吗 25 算法实现题4 15套汇问题 问题描述 套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币 例如 假定1美元可以买0 7英镑 1英镑可以买9 5法郎 且1法郎可以买到0 16美元 通过货币兑换 一个商人可以从1美元开始买入 得到0 7 9 5 0 1
12、6 1 064美元 从而获得6 4 的利润 编程任务 给定n种货币c1 c2 c3 cn的有关兑换率 试设计一个有效算法 用以确定是否存在套汇的可能性 26 输入示例3USDollarBritishPoundFrenchFranc3USDollar0 5BritishPoundBritishPound10 0FrenchFrancFrenchFranc0 21USDollar0输出示例Case1yes 算法实现题4 15套汇问题 数据输入 本题有多个测试数据项 每个测试数据项的第一行中只有1个整数n 1 n 30 表示货币总数 其后n行给出n种货币的名称 接下来的一行中有1个整数m 表示有m种
13、不同的货币兑换率 其后m行给出m种不同的货币兑换率 每行有3个数据项ci rij和cj 表示货币ci和cj的兑换率为rij 文件最后以数字0结束 结果输出 对每个测试数据项j 如果存在套汇的可能性则输出 Casejyes 否则输出 Casejno 27 算法实现题4 15套汇问题 while 1 cin n if n 0 break 输入结束for i 0 i name i 读取货币名称for i 0 i edges 兑换率数目for i 0 i a x b for j 0 strcmp a name j j 确定a的下标for k 0 strcmp b name k k 确定b的下标r j
14、k x 28 算法实现题4 15套汇问题 while 1 for i 0 i1 0 break 搜索赢利情况if i n cout case cases yes endl elsecout case cases no endl 只要搜到一个赢利就行 29 算法实现题4 15套汇问题 3USDollarBritishPoundFrenchFranc6USDollar0 5BritishPoundUSDollar4 9FrenchFrancBritishPound10 0FrenchFrancBritishPound1 99USDollarFrenchFranc0 09BritishPoundFr
15、enchFranc0 19USDollarAnswer no 30 算法实现题4 21区间相交问题 问题描述 给定x轴上n个闭区间 去掉尽可能少的闭区间 使剩下的闭区间都不相交 编程任务 给定n个闭区间 编程计算去掉的最少闭区间数 数据输入 第一行是正整数n 表示闭区间数 接下来的n行中 每行有2个整数 分别表示闭区间的2个端点 结果输出 计算出的去掉的最少闭区间数 输入示例3102010152015输出文件示例2 与活动安排类似if a b swap a b 按右端点从小到大排序 依左端点超过右端点进行选择 31 算法实现题4 21区间相交问题 数据结构 structinterval int
16、start intend 比较函数 boolcmp intervala intervalb if a end b end returntrue elsereturnfalse 32 算法实现题4 21区间相交问题 在intmain 中 intn inta b cin n intervalinte 100 for inti 0 i a b if a b swap a b inte i start a inte i end b sort inte inte n cmp cout n GreedySelector n inte endl 33 算法实现题4 21区间相交问题 贪心选择 intGreedySelector intn intervalinte intcount 1 intj 0 区间的起点for inti 1 iinte j end count j i returncount 34 算法实现题4 23最优分解问题 问题描述 设n是一个正整数 现在要求将n分解为若干个互不相同的自然数的和 且使这些自然数的乘积最大 编程任务 对于给定的正整数n 编程计算最优分解方案 数据输入 第1行
