文档介绍：第十讲贪心与动态规划专题(一)ACM算法与程序设计导引问题:FatMouse'TradeProblemDescriptionFatMousepreparedMpoundsofcatfood,readytotradewiththecatsguardingthewarehousecontaininghisfavoritefood,JavaBean.-throomcontainsJ[i]poundsofJavaBeansandrequiresF[i],instead,hemaygetJ[i]*a%poundsofJavaBeansifhepaysF[i]*a%:-,eachcontainstwonon-negativeintegersJ[i]andF[i]-1',urateupto3decimalplaces,-1-“贪心算法”是指:在对问题求解时,总是作出在当前看来是最好的选择。也就是说,不从整体上加以考虑,它所作出的仅仅是在某种意义上的局部最优解(是否是全局最优,需要证明)。当一个问题的最优解包含着它的子问题的最优解时,称此问题具有最优子结构性质。当一个问题具有最优子结构性质时,我们会想到用动态规划法去解它。但有时会有更简单有效的算法。顾名思义,贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法并不从整体最优上加以考虑,它所作出的选择只是在某种意义上的局部最优选择。用贪心算法更简单,更直接且解题效率更高。虽然贪心算法不是对所有问题都能得到整体最优解,但对范围相当广的许多问题它能产生整体最优解。如图的单源最短路径问题,最小生成树问题等。在一些情况下,即使贪心算法不能得到整体最优解,但其最终结果却是最优解的很好的近似解。特别说明:若要用贪心算法求解某问题的整体最优解,必须首先证明贪心思想在该问题的应用结果就是最优解!!MovingTables./?pid=1050DescriptionThefamousACM(,:,,duringeach10minutes,