ACM程序设计-贪心算法.pptVIP

ACM程序设计 * * 贪心算法（Greedy Algorithm） * * 导引问题：FatMouse Trade * * FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favorite food, JavaBean. The warehouse has N rooms. The i-th room contains J[i] pounds of JavaBeans and requires F[i] pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get J[i]*a% pounds of JavaBeans if he pays F[i]*a% pounds of cat food. Here a is a real number. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain. * * Input The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative integers J[i] and F[i] respectively. The last test case is followed by two -1‘s. All integers are not greater than 1000.? Output For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain. * * Sample Input 5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1? Sample Output 13.333 31.500 * * 所谓“贪心算法”是指： 在对问题求解时，总是作出在当前看来是最好的选择。也就是说，不从整体上加以考虑，它所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。 适用于贪心算法策略求解的大多数问题两个特点： 最优子结构：问题的最优解包含了子问题的最有解。 贪心选择性质：可通过做局部最优选择来达到一个数值递增或递减的序关系。 * * 特别说明： 若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！ * * 一、事件序列问题 已知N个事件的发生时刻和结束时刻（见下表，表中事件已按结束时刻升序排序）。一些在时间上没有重叠的事件，可以构成一个事件序列，如事件 {2，8，10}。事件序列包含的事件数目，称为该事件序列的长度。请编程找出一个最长的事件序列。 事件编号 0 1 2 3 4 5 6 7 8 9 10 11 发生时刻 1 3 0 3 2 5 6 4 10 8 15 15 结束时刻 3 4 7 8 9 10 12 14 15 18 19 20 * * 算法分析： 不妨用Begin[i]和End[i]表示事件i的开始时刻和结束时刻。则原题的要求就是找一个最长的序列a1a2…an，满足： Begin[a1]End[a1]=…= Begin[an]End[an] 可以证明，如果在可能的事件a1a2…an中选取在时间上不重叠的最长序列，那么一定存在一个包含a1（结束最早）的最长序列。 （证明：略） * * 算法设计： 从结束时间最早的事件开始 以后各步从开始事件大于上一步结束事件的事件中寻找最先结束的事件。 事件复杂度O(N) N-总事件数 * * 二、区间覆盖问题 用i来表示x轴上坐标为[i-1,i]的区间（长度为1），并给出M(1=M=200)个不同的整数，表示M个这样的区间。现在让你画几条线段覆盖住所有的区间，条件是：每条线段可以任意长，但是要求所画线段之和最小，并且线段的数目不超