贪心算法习题

1、【问题描述问题描述】 有n个人在一个水龙头前排队接水。假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。【问题描述问题描述】 我们计划组织一个独木舟旅行。租用的独木舟都是一样的，最多乘两人，而且载重有一个限度。现在要节约费用，所以要尽可能地租用最少的舟。你的任务是读入独木舟的载重量，参加旅行的人数以及每个人的体重，计算出所需要的租船数目。【样例输入样例输入】 独木舟载重量：100人数：9体重： 90 20 20 30 50 60 70 80 90基于贪心法，找到一个重量最大的人，让它尽可能与重量大的人同乘一船。如此循环直至所有人都分配完毕即可统计出所需

2、要的独木舟数。【问题描述问题描述】 小伟报名参加电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的！接下来，主持人宣布了比赛规则：首先，比赛时间分为n个时段，它又给出了很多小游戏，每个小游戏都必须在规定期限 ti 前完成（1=ti=n）。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数。不同的游戏扣去的钱数是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，

3、小伟如何赢取最多的钱！【样例样例】输入 初始奖金：10000 游戏个数：7 结束时段：4 2 4 3 1 4 6 罚款金额：70 60 50 40 30 20 10 输出 9950因为不同的小游戏不能准时完成时，具有不同的扣款权数，而且是最优解问题，所以，很容易就想到用贪心法来求解本题。根据贪心思想，应让扣款数值大的尽量准时完成。这样，我们就先把这些任务按照扣款的数目进行排序，把大的排在前面，先进行放置。假如罚款最多的一个任务的完成期限是k，我们应该把它安排在哪个时段完成呢？应该放在第k个时段，因为放在1k中的任何一个位置上时，效果都是一样的。一旦出现一个不可能在规定时限前完成的任务，则把其扔

4、到最大的一个空时间段内。这样做的效果必然是最优的，因为不能完成的任务，在任意一个时间段中罚款数目都是一样的。一位管理项目的经理想要确定每个月一位管理项目的经理想要确定每个月需要的工人数量。他当然知道每月所需需要的工人数量。他当然知道每月所需的最少工人数。当他雇佣或解雇一个工的最少工人数。当他雇佣或解雇一个工人时，会有一些额外支出。一旦一个工人时，会有一些额外支出。一旦一个工人被雇佣，即使他不工作，他也将得到人被雇佣，即使他不工作，他也将得到工资。这位经理知道雇佣一个工人的费工资。这位经理知道雇佣一个工人的费用、解雇一个工人的费用和一个工人的用、解雇一个工人的费用和一个工人的工资。现在，他在考虑

5、一个问题：为了工资。现在，他在考虑一个问题：为了把项目的费用控制在最低水平上，他将把项目的费用控制在最低水平上，他将每月雇佣或解雇多少个工人。每月雇佣或解雇多少个工人。【输入输入】 输入文件含有三行。第一行为月数n（不超过12）。第二行含有雇佣一个工人的费用、一个工人的工资和解雇一个工人的费用（=100）。第三行含n个数，分别表示每月最少需要的工人数（=1000）。每个数据之间有一个空格隔开。【输出输出】 输出仅一行，表示项目的最小总费用。【样例输入样例输入】 3 4 5 6 10 9 11【样例输出样例输出】 199我们从第一个月开始，逐月计算现有工人数，先给这些工人发放工资。如果雇佣了新工

6、人，则必须给新上岗人员发放雇佣费用；如果削减了部分工人，则必须给下岗人员发放解雇费用。当月发放的工资+雇佣（或解雇）费用构成了一个月的总费用。我们从第一个月开始，逐月累计项目总费用，直至计算出n个月的总费用时为止。问题是，怎样将这笔费用控制在最低水平上？设mincost表示最小费用和，初始时，mincost=0；now表示现有工人数，初始时，now=0；mini表示第i个月所需要的最少工人数（1=I now then begin mincost := mincost + h * (mini - now); now := mini; end;mincost := mincost + now *

7、s; 显然，这样的雇佣费用支出是最节省的如果现有工人数now大于第i个月最少需要的工人数mini，则需要解雇一部分工人最佳方案是否一定是解雇（now-mini）个工人呢？不一定是的。例如，对于示例中的数据，依上述方法计算：第1个月雇佣10人：mincost = mincost + h * (mini - now) + s * mini = 0+4*10+5*10 = 90 now = 10 (注意：h=4, s=5, f=6; )第2个月解雇1人，使得现有工人数为9人：mincost = mincost + f * (now - min2)+s * min2 = 90+6*1+9*5 = 14

8、1 now = 9第3个月雇佣2人，使得现有工人数为11人：mincost = mincost + h * (min3 - now) + s * min3 =141+4*2+5*11 = 204 now = 11显然，该雇佣计划的总费用（显然，该雇佣计划的总费用（204204）并）并不是最少的，因为如果第不是最少的，因为如果第2 2个月不解雇个月不解雇1 1人，仍维持人，仍维持1010人，第人，第3 3个月再雇佣个月再雇佣1 1人，人，这种情况下的总费用为（这种情况下的总费用为（4 4* *10+510+5* *1010）+(5+(5* *10)+(410)+(4* *1+51+5* *11)

9、=90+50+59=19911)=90+50+59=199，即为样例输出。即为样例输出。由此看出，解雇的人数应比（now-mini）少一些，那么少多少呢？我们采取这样的贪心策略去确定： 尽可能少地解雇工人(Why?)，并且，在工资支出合理的前提下，尽可能使现有工人数维持在一个最长时间内，以减少雇佣和解雇的额外支出。实现的方法是：在实现的方法是：在miniminnminiminn间，间，按最少需要人数递增的顺序，将月份排按最少需要人数递增的顺序，将月份排成序列成序列y y1 1，y y2 2，y yn-in-i，y yn-i+1n-i+1（其中（其中i=yi=yj j=n=n，1=j=n-i+1

10、1=j=n-i+1）。）。从第yj个月出发，按照最少需要递减的顺序来检查minyj、minyj-1、，一旦发现第yj月超员(问题：为什么是倒序检查？能否正序检查？)，且这些工人在第yj+1个月雇佣与第i到第yj月期间解雇的总费用，比第i到第yj个月连续使用的费用节约，即： （minyjnow）and (f+hs*(yj+1-i) and (yj+1=n) or (fn) 则在第i个月解雇now-minyj个工人，使现有工人数变为minyj，否则，维持现有工人数不变。在miniminn间，按最少需要人数递增的顺序，将月份排成y1，yn-i+1;for j := n i downto 1 do 思考：为何要倒推？ if (minyjnow) and (f+h*ord(yj+1=n) now then if mini now then 在现有人数不足的情况下，确定第在现有人数不足的情况下，确定第i i个月的雇佣方案，个月的雇佣方案， 并累计最小费用并累计最小费用mincost;mincost; else else 在现有人数多余的情况下，确定第在现有人数多余的情况下，确