贪心法例题.pdfVIP

贪 心 法（一） 1、纪念品分组 (group.pas) 【问题描述】 元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学 所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包 括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的 时间内发完所有纪念品，乐乐希望分组的数目最少。 你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数 目。 【输入】 输入文件 group.in 包含n+2 行： 第1 行包括一个整数 w，为每组纪念品价格之和的上限。 第2 行为一个整数 n，表示购来的纪念品的总件数。 第3～n+2 行每行包含一个正整数 p (5=p=w)，表示所对应纪念品的价格。 i i 【输出】 输出文件 group.out 仅一行，包含一个整数，即最少的分组数目。 【输入输出样例】 group.in group.out 100 6 9 90 20 20 30 50 60 70 80 90 【限制】 50％的数据满足：l=n=15 100％的数据满足：1=n=30000，80=w=200 2、独木舟 （kaj.bas） 【问题描述】 我们计划组织一个独木舟旅行。租用的独木舟都是一样的，最多乘两人，而且载重有一 个限度。现在要节约费用，所以要尽可能地租用最少的舟。你的任务是读入独木舟的载重量， 参加旅行的人数以及每个人的体重，计算出所需要的租船数目。 【输入格式】 1 输入文件名为 kaj . in ，其第一行是w （80≤w ≤200 ），表示每条独木舟最大的载重量。 第二行是整数 n （1≤n ≤30000，参加旅行的人数。接下来的 n 行，每行是一个整数 Ti （5 ≤Ti≤w ），表示每个人的重量。 【输出格式】 输出文件仅一行，表示最少的租船数目。 【样例输入】 100 9 90 20 20 30 50 60 70 80 90 【样例输出】 6 3. 修复牛棚 (barn.bas) 【问题描述】 农夫约翰在一个呈一字排开的牛棚里养了一群牛。这个牛棚有很多隔间，每个隔间的 大小都是一样的。一个隔间里只能放一头牛。有的隔间里有牛，有的隔间是空的。 在一个风雨交加的夜晚，暴风雨把牛棚的顶和门都掀掉了。约翰必须迅速在牛棚前竖 起一些新的挡板，因为牛棚的门都没有了。他的木材供应商只能供应给他少量的几块木板， 但每一块可以有任意的长度。约翰要计算一下需要几块木板，并希望使新买的木板的总长度 最小。 现在，已知约翰可以购买的木板的最大数量为 M （1=M=50），牛棚里总的隔间数为 S （1=S=200），牛棚中现有牛的数量为 C （1=C=S），以及这 C 头牛所占据的隔间的编 号（1=隔间编号=S ），请你计算一下，为了挡住所有有牛的隔间，约翰最少需要挡住多少 个隔间？ 【输入】(barn.in) 文件输入，输入文件的名为 barn.in，在该文件中： 第一行是三个数 M 、S 和 C，分别表示最多可以购买的木板数、总的隔间数的牛的数量； 接下来的 C 行中，每一行包含一个