第4章-贪心算法-习题

第四章作业部分参考答案1 • 设有n个顾客同时等待一项服务。

顾客i需要的服务时间为t i,1 i n。

应该如何安排n个顾客的服务次序才能使总的等待时间达到最小？总的等待时间是各顾客等待服务的时间的总和。

试给出你的做法的理由(证明) 。

策略：对t i 1 i n进行排序，h t i2t i n,然后按照递增顺序依次服务i i」2,…,i n即可。

解析：设得到服务的顾客的顺序为j1, j2,..., j n ，则总等待时间为T (n 1)t j i (n 2)t j2 2.? 则在总等待时间T中切的权重最大，切的权重最小。

故让所需时间少的顾客先得到服务可以减少总等待时间。

证明：设t i1 t i2 t i n, ，下证明当按照不减顺序依次服务时，为最优策略。

记按照i1i2 i n 次序服务时，等待时间为T ，下证明任意互换两者的次序，T 都不减。

即假设互换i, j (i j) 两位顾客的次序，互换后等待总时间为T~，则有T T.由于T (n 1)t i1 (n 2)t i2 2t i n2 t,i n 1T (n 1)t i1 (n 2)t i2 (n i)t i i (n j)t i j 2t ti n 2 i n 1T (n 1)t i1 (n 2)t i2 (n i)t i j (n j)t i i 2t i t ii n 2 i n 1则有T~ T (j i)(t i j t i i ) 0.同理可证其它次序，都可以由i1i2 i n 经过有限次两两调换顺序后得到，而每次交换，总时间不减，从而i1i 2 i n 为最优策略2. 字符a ~h 出现的频率分布恰好是前 8个Fibo nacci 数，它们的Huffman编码是什么？将结果推广到n 个字符的频率分布恰好是前n 个Fibonacci 数的情 形。

Fib on acci 数的定义为：F o1,F i 1, F nF n 2 F n 1 if n 1所以a 的编码为：1111111 b 的编码为：1111110 c 的编码为：111110 d 的编码为：11110 e 的编码为：1110 f 的编码为：110 g 的编码为：10 h 的编码为：0 推广到 n 个字符：第 1 个字符： n-1 个 1 ，11 1n1 第 2 个字符： n-2 个1 ， 1 个 0， 11 10n2第 3 个字符： n-3 个 1 ，1 个 0， 11 10n3第n-1个字符：1个1 ， 1 个 0， 10 第 n 个字符： 1 个 03． 设 p 1,p 2, ,p n 是准备存放到长为 L 的磁带上的 n 个程序，程序 p i 需要的 n 带长为 a i 。

第四章-贪⼼算法（模拟试题）计算机与信息科学学院2010-2011学年第2学期模拟试卷计算机算法设计与分析—第四章.贪⼼算法本卷满分100分完卷时间120分钟⼀. 简答题（每⼩题2分，共20分）1. 当⼀个问题具有且具有时可⽤贪⼼算法，如最⼩⽣成树问题（背包问题，活动安排问题等）。

2. 在动态规划可⾏的基础上满⾜才能⽤贪⼼。

3. 贪⼼算法总是作出在当前看来最好的选择。

也就是说贪⼼算法并不从整体最优考虑，它所作出的选择只是在某种意义上的选择。

4. 动态规划算法通常以的⽅式解各⼦问题，⽽贪⼼算法则通常以的⽅式进⾏，以迭代的⽅式作出相继的贪⼼选择，每作⼀次贪⼼选择就将所求问题简化为规模更⼩的⼦问题5. 贪⼼算法和动态规划算法都要求问题具有性质，这是2类算法的⼀个共同点。

6. 当⼀个问题的最优解包含其⼦问题的最优解时，称此问题具有。

7. 对于具有n 个顶点和e 条边的带权有向图，如果⽤带权邻接矩阵表⽰这个图，那么Dijkstra 算法的主循环体需要时间。

这个循环需要执⾏n-1次，所以完成循环需要时间。

算法的其余部分所需要时间不超过。

8. 0-1背包问题指：给定n 种物品和⼀个背包。

物品i 的重量是Wi ，其价值为Vi ，背包的容量为C 。

应如何选择装⼊背包的物品，使得装⼊背包中物品的最⼤。

9. 有⼀批集装箱要装上⼀艘载重量为c 的轮船。

其中集装箱i 的重量为Wi 。

最优装载问题要求确定在不受限制的情况下，将装上轮船。

10. 多机调度问题要求给出⼀种作业调度⽅案，使所给的n 个作业在由m 台机器加⼯处理完成。

⼆. 综合题（1-6题每题7分，7-8题每题9分，共60分）1. 有4个物品，其重量分别为(4, 7, 5, 3)，物品的价值分别为(40, 42, 25,12)，背包容量为10。

试设计3种贪⼼策略,并给出在每种贪⼼策略下背包问题的解。

)(n O2. 使⽤prim算法构造出如下图G的⼀棵最⼩⽣成树。

dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)=63. 设有n项独⽴的作业{1,2,…, n},由m台相同的机器加⼯处理。

贪心算法及几个常用的例题贪心算法：一、基本概念：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。

必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

二、贪心算法的基本思路：1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

三、贪心算法适用的问题贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

实际上，贪心算法适用的情况很少。

一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

四、贪心算法的实现框架从问题的某一初始解出发；while （能朝给定总目标前进一步）利用可行的决策，求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；五、贪心策略的选择因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。

几个经典的例子：一、定义什么是贪心算法呢？所谓贪心算法是指，在对问题求解时，总是做出在当前看来最好的选择。

也就是说，不从整体最优解出发来考虑，它所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题都能产生整体最优解或整体最优解的近似解。

贪心算法的基本思路如下：1. .建立数学模型来描述问题。

2. 把求解的问题分成若干个子问题。

3. 对每个子问题求解，得到每个子问题的局部最优解。

4. 把每个子问题的局部最优解合成为原来问题的一个解。

江西科学技术版小学信息技术五年级下册《主题活动：贪心算法》同步练习题附知识点归纳一、课文知识点归纳：1. 贪心算法的基本概念：（1）贪心算法是一种求解最优解问题的更简单、更迅速的设计技术。

（2）它以当前情况为基础，根据某个优化测度做出最优选择，而不考虑所有可能的整体情况。

（3）贪心算法通过自顶向下、迭代的方法做出相继的贪心选择，每做一次选择，问题就简化为一个规模更小的子问题。

2. 贪心算法的基本要素：（1）贪心选择性质：整体最优解可通过一系列局部最优解的选择达到，且每次选择不依赖于后续选择。

（2）最优子结构性质：问题的最优解包含其子问题的最优解。

3.贪心算法的步骤：（1）建立数学模型来描述问题。

（2）把求解的问题分成若干个子问题。

（3）对每个子问题求解，得到子问题的局部最优解。

（4）将子问题的局部最优解合成原问题的解。

4.贪心算法的特点：（1）简单易实现，计算效率高。

（2）适用于具有贪心选择性质和最优子结构性质的问题。

（3）得到的解通常是某种意义上的局部最优解，但不一定是全局最优解。

5.贪心算法的应用场景：（1）货币兑换问题（如找零钱问题）。

（2）背包问题（在限制条件下选择最大价值的物品）。

（3）活动选择问题（安排一系列活动使得尽可能多的活动被安排）。

二、同步练习题。

（一）、填空题。

1. 贪心算法是一种在每一步选择中都采取在当前状态下最好或最优__________的选择，从而希望导致结果是全局最好或最优的算法。

2. 在解决背包问题时，如果背包容量为20千克，物品A重5千克价值100元，物品B重10千克价值150元，为了价值最大化，应先放入____________千克的物品。

3. 在活动选择问题中，若有多个活动的时间区间存在冲突，我们通常使用____________算法进行筛选。

（二）、选择题。

1. 下列关于贪心算法的说法，正确的是（）。

A. 贪心算法总是能得到全局最优解B. 贪心算法是一种启发式搜索算法C. 贪心算法只适用于特定类型的问题D. 贪心算法不需要考虑问题的整体结构2. 在教室调度问题中，若某间教室在某天的课程安排如下：课程A 9:00-10:00，课程B 9:30-10:30，课程C 10:30-11:30，则能在这间教室连续进行的课程是（）。

贪⼼算法（4）：作业排序问题上⼀堂课程，我们学习了如何选择活动，使得在不发⽣冲突的前提下，能参与尽可能多的活动，这⾥没有考虑到不同的活动是否会带来不同的收益，假设它们的收益是⼀样的。

现在我们把问题修改下：有⼀系列作业，每个作业必须在各⾃的截⽌时间点之前完成，并且已知完成每个⼯作需要花费的时间以及带来的收益。

为了简单起见，假设完成每个⼯作都需要相等的单位时间，这样作业的截⾄时间点也就是单位时间的倍数。

再假设⼀次只能安排⼀个作业，完成⼀个作业后才能继续下⼀个作业。

问：如何选择作业并安排次序使它们能带来的总收益为最⼤？我们⽤例⼦A来说明。

【输⼊】有4个作业a,b,c,d。

它们各⾃的截⽌时间和能带来的收益如下：【输出】请找出⼀种能带来最⼤收益的作业执⾏次序。

在例⼦中，下列作业次序能带来最⼤的收益：｛c, a｝完成作业c，能带来的收益是40；因为做作业c，截⽌时间为1，它必须安排在0-1之间执⾏。

这样已经错过了b或d的截⽌时间点（1），因此⽆法再选择b或d，只能选择作业a，a的截⾄时间点为4，来得及完成。

做作业a的收益是20，因此完成作业c和a能带来的总收益是 40+20=60。

⽽选择其他次序的作业，都⽆法超过收益60。

参见下⾯的动图：我们再看⼀个例⼦B【输⼊】有5个作业a,b,c,d,e。

它们各⾃的截⽌时间和能带来的收益如下：请你选择和安排能获取最⼤收益的作业次序，先不给出答案，请你先思考，如何解答，然后再继续阅读。

算法分析⼀个简单粗暴的算法就是⽣成给定作业集合的所有⼦集，并检查每⼀个⼦集以确定该⼦集中作业的可⾏性，然后找出哪个可⾏⼦集可以产⽣最⼤收益。

这是⼀个典型的贪⼼算法。

算法思路如下：1）根据收益递减顺序对所有作业进⾏排序。

2）将结果序列初始化，并把已排序作业中的第⼀个作业加⼊3）依次按下⾯的规则处理剩余的n-1个作业如果把当前作业加⼊结果序列，不会错过它的截⽌时间，那么把它加⼊结果序列；否则忽略当前的作业。

贪心算法练习题贪心算法1.喷水装置（一）描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。

输入第一行m表示有m组测试数据每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。

输出输出所用装置的个数样例输入252 3.2 4 4.5 6101 2 3 1 2 1.2 3 1.1 1 2样例输出25根据日常生活知道，选择半径越大的装置，所用的数目越少。

因此，可以先对半径排序，然后选择半径大的。

另外，当装置刚好喷到矩形的顶点时，数目最少。

此时只要装置的有效喷水距离的和不小于20时，输出此时的装置数目即可。

2.喷水装置（二）时间限制：3000 ms | 内存限制：65535 KB难度：4描述有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。

请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。

输入第一行输入一个正整数N表示共有n次测试数据。

每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。

随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。

输出每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。

如果不存在一种能够把整个草坪湿润的方案，请输出0。

样例输入22 8 61 14 52 10 64 56 5样例输出123.会场安排问题描述学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。

贪心法3.1 排队接水有n 个人在一个水龙头前排队接水，假如每个人接水的时间为T i ，请编程找出这n 个人排队的一种顺序，使得n 个人的平均等待时间最小。

【输入】输入文件共两行，第一行为n ；第二行分别表示第1个人到第n 个人每人的接水时间T 1，T 2，…，T n ，每个数据之间有1个空格。

【输出】输出文件有两行，第一行为一种排队顺序，即1到n 的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

【样例】 water.in water.out 10 3 2 7 8 1 4 9 6 10 5 56 12 1 99 1000 234 33 55 99 812 291.90 【算法分析】 平均等待时间是每个人的等待时间之和再除以n ，因为n 是一个常数，所以等待时间之和最小，也就是平均等待时间最小。

假设是按照1~n 的自然顺序排列的，则这个问题就是求以下公式的最小值：∑∑==⎪⎪⎭⎫⎝⎛=+⋯⋯+++⋯⋯++++++=ni i j j n T T T T T T T T T T total 1121321211)()()(如果用穷举的方法求解，就需要我们产生n 个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行n!次求和以及判断，时间复杂度很差！ 其实，我们认真研究一下上面的公式，发现可以改写成如下形式：∑=--+=++⋯⋯+-+-+=ni i n n T i n T T T n T n nT total 11321)1(2)2()1(这个公式何时取最小值呢？对于任意一种排列k 1, k 2, k 3, …, k n ，当1k T ≤2k T ≤3k T ≤…≤n k T 时，total取到最小值。

如何证明呢？方法如下： 因为n j i k k k k k T T j n T i n T n nT total +⋯++-+⋯++-+⋯+-+=)1()1()1(21假设i <j ，而i k T <j k T ，这是的和为total 1，而把k i 和kj 互换位置，设新的和为total 2，则：))(())(1())(1())1()1(()1()1(12i j i j i j j i i j k k k k k k k k k k T T i j T T j n T T i n T j n T i n T j n T i n total total total --=-+---+-=+-++--+-++-=-=∆我们发现上述△total 恒大于0，所以也说明了任何次序的改变，都会导致等待时间的增加。

算法作业——第4章贪⼼算法第4章 贪⼼算法 习题贪⼼算法 习题第4章【+】阅读、掌握课本经典范例代码的实现：（1）活动安排问题；（2）最优装载问题；（3）哈夫曼编码；（4）单源最短路径；（5）最⼩⽣成树；（6）多机调度问题。

【第1题】单项选择题（1）下⾯是贪⼼算法的基本要素的是（ ）。

A.重叠⼦问题B.构造最优解C.贪⼼选择性质D.定义最优解（2）下⾯问题（ ）不能使⽤贪⼼法解决。

A.单源最短路径问题B. n皇后问题C.最⼩花费⽣成树问题D.背包问题（3）采⽤贪⼼算法的最优装载问题的主要计算量在于将集装箱依其重量从⼩到⼤排序，故算法的时间复杂度为（ ）。

A.O(n)B.O(n2)C.O(n3)D.O(nlog2n)（4）关于0-1背包问题以下描述正确的是（ ）。

A.可以使⽤贪⼼算法找到最优解B.能找到多项式时间的有效算法C.使⽤教材介绍的动态规划⽅法可求解任意0-1背包问题D.对于同⼀背包与相同的物品，做背包问题取得的总价值⼀定⼤于等于做0-1背包问题（5）⼀棵哈夫曼树共有215个结点，对其进⾏哈夫曼编码，共能得到（ ）个不同的码字。

A.107B.108C.214D.215【第2题】求解哈夫曼编码中如何体现贪⼼思路？【第3题】举反例证明0-1背包问题若使⽤的算法是按照vi/wi的⾮递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装⼊背包，则此⽅法不⼀定能得到最优解（此题说明0-1背包问题与背包问题的不同）。

*【第4题】给定数轴X上n个不同点的集合，{x1,x2,...,xn}，其中，x1<x2<...<xn。

现在⽤若⼲个长度为1的闭区间来覆盖这些点。

设计⼀个算法找到最少的闭区间个数和位置。

证明算法的正确性并估计算法的时间复杂度。

【第5题】（编程）求解硬币问题。

有1分、2分、5分、10分、50分和100分的硬币各若⼲枚，现在要⽤这些硬币来⽀付W元，最少需要多少枚硬币。

说明：⽤结构体数组A存放硬币数据，A[i].v存放硬币i的⾯额，A[i].c存放硬币i的枚数。

贪⼼算法-例题讲解前⾔：此博客在写作过程中参考了⼤量资料和博客，不能⼀⼀列举，还请见谅。

概述贪⼼法：从问题的某⼀个初始状态出发，逐步构造最优解从⽽向⽬标前进，并期望通过这种⽅法产⽣出⼀个全局最优解的⽅法贪⼼是⼀种解题策略，也是⼀种解题思想，⽽不是算法贪⼼策略与其他算法的区别贪⼼与递推：贪⼼法推进每⼀步不依据某⼀固定的递推式，⽽是当前看似最佳的贪⼼决策，不断的将问题归纳为更加⼩的相似的⼦问题贪⼼与动态规划：贪⼼是“⿏⽬⼨光”；动态规划是“统揽全局”贪⼼法的优缺点优点：思维复杂度低、代码量⼩、运⾏效率⾼、空间复杂度低等缺点：很难找到⼀个简单可⾏并且保证正确的贪⼼思路贪⼼算法的应⽤贪⼼算法的常⽤范围有明显的贪⼼可证明贪⼼策略的贪⼼(最常见的)贪⼼数据结构:堆/Kruskal/Prim/Dijkstra博弈/游戏策略，这些策略⼤多是贪⼼求较优解或多次逼近求最优解⼏个简单的贪⼼例⼦最优装载问题：给n个物体，第i个物体重量为wi，选择尽量多的物体，使得总重量不超过C贪⼼策略：先拿轻的部分背包问题：有n个物体，第i个物体的重量为wi，价值为vi，在总重量不超过C的情况下让总价值尽量⾼。

每⼀个物体可以只取⾛⼀部分，价值和重量按⽐例计算贪⼼策略：先拿性价⽐⾼的乘船问题：有n个⼈，第i个⼈重量为wi。

每艘船的载重量均为C，最多乘两个⼈。

⽤最少的船装载所有⼈贪⼼策略：最轻的⼈和最重的⼈配对例题(基础)1.删数问题-【问题描述】键盘输⼊⼀个⾼精度的正整数n（n<=240位）,去掉其中任意s个数字后剩下的数字按照原来的次序将组成⼀个新的正整数。

编程对给定的n和s,寻求⼀种⽅案,使得剩下组成的新数最⼩。

贪⼼策略为：每⼀步总是选择⼀个使剩下的数最⼩的数字删去，即按⾼位到低位的顺序搜索，若各位数字递增，则删除最后⼀个数字，否则删除第⼀个递减区间的⾸字符。

然后回到串⾸，按上述规则再删除下⼀个数字。

重复以上过程s次，剩下的数字串便是问题的解了。

贪心法3.1 排队接水有n 个人在一个水龙头前排队接水，假如每个人接水的时间为T i ，请编程找出这n 个人排队的一种顺序，使得n 个人的平均等待时间最小。

【输入】输入文件共两行，第一行为n ；第二行分别表示第1个人到第n 个人每人的接水时间T 1，T 2，…，T n ，每个数据之间有1个空格。

【输出】输出文件有两行，第一行为一种排队顺序，即1到n 的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

【样例】 water.in water.out 10 3 2 7 8 1 4 9 6 10 5 56 12 1 99 1000 234 33 55 99 812 291.90 【算法分析】 平均等待时间是每个人的等待时间之和再除以n ，因为n 是一个常数，所以等待时间之和最小，也就是平均等待时间最小。

假设是按照1~n 的自然顺序排列的，则这个问题就是求以下公式的最小值：∑∑==⎪⎪⎭⎫⎝⎛=+⋯⋯+++⋯⋯++++++=ni i j j n T T T T T T T T T T total 1121321211)()()(如果用穷举的方法求解，就需要我们产生n 个人的所有不同排列，然后计算每种排列所需要等待的时间之和，再“打擂台”得到最小值，但这种方法需要进行n!次求和以及判断，时间复杂度很差！ 其实，我们认真研究一下上面的公式，发现可以改写成如下形式：∑=--+=++⋯⋯+-+-+=ni i n n T i n T T T n T n nT total 11321)1(2)2()1(这个公式何时取最小值呢？对于任意一种排列k 1, k 2, k 3, …, k n ，当1k T ≤2k T ≤3k T ≤…≤n k T 时，total取到最小值。

如何证明呢？方法如下： 因为n j i k k k k k T T j n T i n T n nT total +⋯++-+⋯++-+⋯+-+=)1()1()1(21假设i <j ，而i k T <j k T ，这是的和为total 1，而把k i 和kj 互换位置，设新的和为total 2，则：))(())(1())(1())1()1(()1()1(12i j i j i j j i i j k k k k k k k k k k T T i j T T j n T T i n T j n T i n T j n T i n total total total --=-+---+-=+-++--+-++-=-=∆我们发现上述△total 恒大于0，所以也说明了任何次序的改变，都会导致等待时间的增加。

喷水装置（一）时间限制：3000 ms | 内存限制：65535 KB难度：3描述现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0<Ri<15)的圆被湿润，这有充足的喷水装置i（1<i<600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。

输入第一行m表示有m组测试数据每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。

输出输出所用装置的个数输入第一行输入一个正整数N表示共有n次测试数据。

每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。

随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。

输出每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。

如果不存在一种能够把整个草坪湿润的方案，请输出0。

输入第一行是一个整型数m(m<100)表示共有m组测试数据。

每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。

随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)输出对于每一组输入，输出最多能够安排的活动数量。

每组的输出占一行样例输入样例输出12Gone Fishing时间限制：3000 ms | 内存限制：65535 KB难度：5描述John is going on a fishing trip. He has h hours available (1 <= h <= 16), and there are n lakes in the area (2 <= n <= 25) all reachable along a single, one-way road.John starts at lake 1, but he can finish at any lake he wants. He can only travelfrom one lake to the next one, but he does not have to stop at any lake unless he wishes to. For each i = 1,...,n - 1, the number of 5-minute intervals it takes totravel from lake i to lake i + 1 is denoted ti (0 <ti<=192). For example, t3 = 4means that it takes 20 minutes to travel from lake 3 to lake 4. To help plan hisfishing trip, John has gathered some information about the lakes. For each lake i, the number of fish expected to be caught in the initial 5 minutes, denoted fi( fi >=0 ), is known. Each 5 minutes of fishing decreases the number of fish expected tobe caught in the next 5-minute interval by a constant rate of di (di >= 0). If thenumber of fish expected to be caught in an interval is less than or equal to di ,there will be no more fish left in the lake in the next interval. To simplify theplanning, John assumes that no one else will be fishing at the lakes to affect thenumber of fish he expects to catch.Write a program to help John plan his fishing trip to maximize the number of fish expected to be caught. The number of minutes spent at each lake must be amultiple of 5.输入You will be given a number of cases in the input. Each case starts with a linecontaining n. This is followed by a line containing h. Next, there is a line of nintegers specifying fi (1 <= i <=n), then a line of n integers di (1 <=i <=n), andfinally, a line of n - 1 integers ti (1 <=i <=n - 1). Input is terminated by a case in which n = 0.输出For each test case, print the number of minutes spent at each lake, separated by commas, for the plan achieving the maximum number of fish expected to becaught (you should print the entire plan on one line even if it exceeds 80characters). This is followed by a line containing the number of fish expected.If multiple plans exist, choose the one that spends as long as possible at lake 1,even if no fish are expected to be caught in some intervals. If there is still a tie,choose the one that spends as long as possible at lake 2, and so on. Insert a blank line between cases.过河问题时间限制：1000 ms | 内存限制：65535 KB难度：5描述在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。