文档介绍：贪婪的动态规划贪婪的动态规划——浅谈贪心思想在动态规划中的应用绍兴县柯桥中学黄劲松引言转移困难在动态规划的解题中我们面临着两大困难 1、不知道是否可以用动态规划求解 2、直观的动态规划算法过于低效在这个时候,巧妙的使用贪心思想,将其融入到动态规划中,动态规划便焕发出了新的光彩状态过于庞大目录?贪心思想在动态规划中的应用?确立状态[例一]青蛙的烦恼(详见论文) [例二] The Horse Racing ?优化算法[例三]石子归并(详见论文) [例四] The Lost House 贪心思想在动态规划中的应用一: 确立状态?动态规划当中,状态的确立是重点?而在实际的解题过程中,状态信息往往是隐含的?这个时候,合理的运用贪心思想,可以迅速的从繁芜丛杂的问题背景中巧妙地抽象出状态[例二]The Horse Racing ?齐王和田忌各派出 N匹马( N≤ 2000 ) ?每匹马都有一个固定的速度值?每场比赛,输的一方将要给赢的一方 200 两黄金,如果是平局的话,双方都不必拿出钱?请你扮演一下孙膑,帮助田忌赢最多的钱时间复杂度过大,无法满足要求[例二] The Horse Racing ?这个问题很显然可以转化成一个二分图最佳匹配的问题?把田忌的马放左边,把齐王的马放右边如果田忌的马胜,则连一条权为 200 的边; 如果平局,则连一条权为 0的边; 如果输,则连一条权为-200 的边。田忌齐王 200 0 -200 [例二] The Horse Racing ?运用贪心思想分析问题: ?田忌掌握有比赛的“主动权”,他总是根据齐王所出的马来分配自己的马去对抗齐王的马?可以假设齐王按照马的强弱顺序由强到弱出马齐王最强的马田忌最强的马用田忌最差的马去输给齐王最强的马输给能赢用田忌最强的马去战胜齐王最强的马战平用田忌最强的马去打平齐王最强的马或者用田忌最差的马去输给齐王最强的马?最强的马战平时,单一的贪心策略存在反例?光是打平比赛田忌的马 1 2 3 齐王的马 1 2 3 [例二] The Horse Racing 收益为 0收益为 200 ?最强的马战平时,单一的贪心策略存在反例?光是输掉比赛田忌的马 2 3 齐王的马 1 3 [例二] The Horse Racing 收益为 200 收益为 0 ?“田忌出马不是出最强的,就是出最弱的”?用f[i,j]表示齐王出了 i匹较强的马和田忌的 j匹较强的马, i-j匹较弱的马比赛之后,田忌所能够得到的最大盈利。?其中 g[i,j]表示齐王和田忌的马分别按由强到弱的顺序排序之后,田忌的第 i匹马和齐王的第 j匹马赛跑所能取得的盈利,胜为 200 ,负为-200 ,平为 0。[例二] The Horse Racing i]} g[j, 1]-j 1,- f[i i], 1, j)- (i- g[n j] 1,- max{f[i j] f[i,???? O( n 2)