欢迎来到天天文库
浏览记录
ID:62119105
大小:102.67 KB
页数:31页
时间:2021-04-12
《贪心算法习题.pptx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、贪心算法习题排队接水【问题描述】有n个人在一个水龙头前排队接水。假如每个人接水的时间为Ti,请编程找出这n个人排队的一种顺序,使得n个人的平均等待时间最小。独木舟【问题描述】我们计划组织一个独木舟旅行。租用的独木舟都是一样的,最多乘两人,而且载重有一个限度。现在要节约费用,所以要尽可能地租用最少的舟。你的任务是读入独木舟的载重量,参加旅行的人数以及每个人的体重,计算出所需要的租船数目。【样例输入】独木舟载重量:100人数:9体重:902020305060708090算法分析基于贪心法,找到一个重量最大的人,让它尽可能与重量大的人同
2、乘一船。如此循环直至所有人都分配完毕即可统计出所需要的独木舟数。智力大冲浪【问题描述】小伟报名参加电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者,主持人为了表彰大家的勇气,先奖励每个参赛者m元。先不要太高兴!因为这些钱还不一定都是你的!接下来,主持人宣布了比赛规则:问题描述首先,比赛时间分为n个时段,它又给出了很多小游戏,每个小游戏都必须在规定期限ti前完成(1<=ti<=n)。如果一个游戏没能在规定期限前完成,则要从奖励费m元中扣去一部分钱wi,wi为自然数。不同的游戏扣去的钱数是不一样的。问题描述当然,每个游戏本身都很简单
3、,保证每个参赛者都能在一个时段内完成,而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者,小伟如何赢取最多的钱!【样例】输入初始奖金:10000游戏个数:7结束时段:4243146罚款金额:70605040302010输出9950分析因为不同的小游戏不能准时完成时,具有不同的扣款权数,而且是最优解问题,所以,很容易就想到用贪心法来求解本题。根据贪心思想,应让扣款数值大的尽量准时完成。这样,我们就先把这些任务按照扣款的数目进行排序,把大的排在前面,先进行放置。假如罚款最多的一个任务的完成期限是
4、k,我们应该把它安排在哪个时段完成呢?应该放在第k个时段,因为放在1~k中的任何一个位置上时,效果都是一样的。分析一旦出现一个不可能在规定时限前完成的任务,则把其扔到最大的一个空时间段内。这样做的效果必然是最优的,因为不能完成的任务,在任意一个时间段中罚款数目都是一样的。雇佣计划一位管理项目的经理想要确定每个月需要的工人数量。他当然知道每月所需的最少工人数。当他雇佣或解雇一个工人时,会有一些额外支出。一旦一个工人被雇佣,即使他不工作,他也将得到工资。这位经理知道雇佣一个工人的费用、解雇一个工人的费用和一个工人的工资。现在,他在考虑
5、一个问题:为了把项目的费用控制在最低水平上,他将每月雇佣或解雇多少个工人。【输入】输入文件含有三行。第一行为月数n(不超过12)。第二行含有雇佣一个工人的费用、一个工人的工资和解雇一个工人的费用(<=100)。第三行含n个数,分别表示每月最少需要的工人数(<=1000)。每个数据之间有一个空格隔开。【输出】输出仅一行,表示项目的最小总费用。【样例输入】345610911【样例输出】199问题分析我们从第一个月开始,逐月计算现有工人数,先给这些工人发放工资。如果雇佣了新工人,则必须给新上岗人员发放雇佣费用;如果削减了部分工人,则必须
6、给下岗人员发放解雇费用。问题分析当月发放的工资+雇佣(或解雇)费用构成了一个月的总费用。我们从第一个月开始,逐月累计项目总费用,直至计算出n个月的总费用时为止。问题是,怎样将这笔费用控制在最低水平上?问题分析设mincost表示最小费用和,初始时,mincost=0;now表示现有工人数,初始时,now=0;min[i]表示第i个月所需要的最少工人数(1<=I<=n);n表示月数,f表示解雇费用,s表示工资,h表示雇佣费用。那么,我们需要解决下面的两个问题:怎样在当月工人数不足的情况下,确定雇佣方案;怎样在当月工人数多余的情况下确
7、定解雇方案。怎样在当月工人数不足的情况下,确定雇佣方案如果第i个月所需的最少人数min[i]大于现有工人数now,则需要雇佣工人。为了尽可能少减少雇佣费用,我们不妨雇佣(min[i]-now)个工人,使得第i个月的工人数正好为min[i]。如果min[i]=now,则维持现有工人数now不变。算法思想如下:ifmin[i]>nowthenbeginmincost:=mincost+h*(min[i]-now);now:=min[i];end;mincost:=mincost+now*s;{显然,这样的雇佣费用支出是最节省的}怎样在
8、当月工人数多余的情况下确定解雇方案如果现有工人数now大于第i个月最少需要的工人数min[i],则需要解雇一部分工人最佳方案是否一定是解雇(now-min[i])个工人呢?不一定是的。例如,对于示例中的数据,依上述方法计算:第1个月雇佣10人:mi
此文档下载收益归作者所有