10 贪心与动态规划专题(一)-课件【PPT讲稿】.ppt

第十讲贪心与动态规划专题(一) ACM 算法与程序设计 2 /31 导引问题: FatMouse ' Trade 3 /31 ? Problem Description 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. 4 /31 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. 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 -1 -1 Sample Output 5 /31 所谓“贪心算法”是指: 在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。 6 /31 ?当一个问题的最优解包含着它的子问题的最优解时,称此问题具有最优子结构性质。?当一个问题具有最优子结构性质时,我们会想到用动态规划法去解它。但有时会有更简单有效的算法。顾名思义,贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑,它所作出的选择只是在某种意义上的局部最优选择。?用贪心算法更简单,更直接且解题效率更高。虽然贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它能产生整体最优解。如图的单源最短路径问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好的近似解。 7 /31 特别说明: 若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!! 8 /31 Moving Tables http:// ./?pid =1050 ? Description The famous ACM (puter Maker) Company has rented a floor of a building whose shape is in the following figure. 9 /31 The floor has 200 rooms each on the north side and south side along the corridor. Recently pany made a plan to reform its system. The reform includes moving a lot of tables between rooms. Because th