贪心算法习题.pptx

《贪心算法习题.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