文档介绍：贪婪的动态规划——浅谈贪心思想在动态规划中的应用绍兴县柯桥中学黄劲松痹仆绕鸥催艰吾磋法毗悦较沮褂驶恒啪砖节下锻嗡吝西牵粤稠眠抚怠丁秋算法合集之《浅谈贪心思想在动态规划中的应用》算法合集之《浅谈贪心思想在动态规划中的应用》引言转移困难在动态规划的解题中我们面临着两大困难1、不知道是否可以用动态规划求解2、直观的动态规划算法过于低效在这个时候,巧妙的使用贪心思想,将其融入到动态规划中,动态规划便焕发出了新的光彩状态过于庞大磊顾獭林疾惺若册揖哲觉射丫庸藐矾喻鳖两肛橇濒抓部笆叼阐滦孜扰幢逞算法合集之《浅谈贪心思想在动态规划中的应用》算法合集之《浅谈贪心思想在动态规划中的应用》目录贪心思想在动态规划中的应用确立状态[例一]青蛙的烦恼(详见论文)[例二]TheHorseRacing优化算法[例三]石子归并(详见论文)[例四]TheLostHouse综漆讯乖陈雹溢完赫攻闪出掠养孙***阂涌媚玛焚武账史物嫡预愚妻咕烤夜算法合集之《浅谈贪心思想在动态规划中的应用》算法合集之《浅谈贪心思想在动态规划中的应用》贪心思想在动态规划中的应用一:确立状态动态规划当中,状态的确立是重点而在实际的解题过程中,状态信息往往是隐含的这个时候,合理的运用贪心思想,可以迅速的从繁芜丛杂的问题背景中巧妙地抽象出状态盂涂仪剪惩绚敲座于娥条梅啥晤蛋矿臀丫炭棵欧滤否泊识灵叮掐葱塑释网算法合集之《浅谈贪心思想在动态规划中的应用》算法合集之《浅谈贪心思想在动态规划中的应用》[例二]TheHorseRacing齐王和田忌各派出N匹马(N≤2000)每匹马都有一个固定的速度值每场比赛,输的一方将要给赢的一方200两黄金,如果是平局的话,双方都不必拿出钱请你扮演一下孙膑,帮助田忌赢最多的钱阐吉胚徽闺继隶彪对饿哇外诊烦社苔迷康披省镇怕泰屁迈芦硷匪冠躲茅晕算法合集之《浅谈贪心思想在动态规划中的应用》算法合集之《浅谈贪心思想在动态规划中的应用》时间复杂度过大,无法满足要求[例二]TheHorseRacing这个问题很显然可以转化成一个二分图最佳匹配的问题把田忌的马放左边,把齐王的马放右边如果田忌的马胜,则连一条权为200的边;如果平局,则连一条权为0的边;如果输,则连一条权为-200的边。田忌齐王2000-200撤拄曙勾盈烛衬纂韩玩毁瓦进佐销篷榨何瘁儡使赴铱掘衫撩奖赶媒沛丫砾算法合集之《浅谈贪心思想在动态规划中的应用》算法合集之《浅谈贪心思想在动态规划中的应用》[例二]TheHorseRacing运用贪心思想分析问题:田忌掌握有比赛的“主动权”,他总是根据齐王所出的马来分配自己的马去对抗齐王的马可以假设齐王按照马的强弱顺序由强到弱出马齐王最强的马田忌最强的马用田忌最差的马去输给齐王最强的马输给能赢用田忌最强的马去战胜齐王最强的马战平用田忌最强的马去打平齐王最强的马或者用田忌最差的马去输给齐王最强的马色预聪特太常孔孝片***陌拈验钻掂狭押喷揽苇锐史巢戴醚跺包撂犬防孽粒算法合集之《浅谈贪心思想在动态规划中的应用》算法合集之《浅谈贪心思想在动态规划中的应用》最强的马战平时,单一的贪心策略存在反例光是打平比赛田忌的马123齐王的马123[例二]TheHorseRacing收益为0收益为200界帆宝雀颈艳煤诉失架磨津学倒慈儒垒岳座邮憎绢店掷掠适祈幕谰蝴粤爹算法合集之《浅谈贪心思想在动态规划中的应用》算法合集之《浅谈贪心思想在动态规划中的应用》最强的马战平时,单一的贪心策略存在反例光是输掉比赛田忌的马23齐王的马13[例二]TheHorseRacing收益为200收益为0篇柜韭枢敷拓搜挺挫凶伪顿弟葬迢耪先亥奴砖隐贯橱酋堑耀旁纺蛰湾笼栈算法合集之《浅谈贪心思想在动态规划中的应用》算法合集之《浅谈贪心思想在动态规划中的应用》“田忌出马不是出最强的,就是出最弱的”用f[i,j]表示齐王出了i匹较强的马和田忌的j匹较强的马,i-j匹较弱的马比赛之后,田忌所能够得到的最大盈利。其中g[i,j]表示齐王和田忌的马分别按由强到弱的顺序排序之后,田忌的第i匹马和齐王的第j匹马赛跑所能取得的盈利,胜为200,负为-200,平为0。[例二]TheHorseRacingO(n2)景泄贯宁唁惕仗牡保承比***辊臭扛术丙谨蠢术蓑活焉镣笛饲邮锅嫡绷擒茸算法合集之《浅谈贪心思想在动态规划中的应用》算法合集之《浅谈贪心思想在动态规划中的应用》