算法合集之浅谈贪心思想在动态规划中的应用学习教案

1、会计学1算法合集之浅谈贪心算法合集之浅谈贪心(tnxn)思想在动态规思想在动态规划中的应用划中的应用第一页，共23页。转移(zhuny)困难p 在动态规划的解题中我们面临着两大困难在动态规划的解题中我们面临着两大困难p 1、不知道、不知道(zh do)是否可以用动态规划求解是否可以用动态规划求解p 2、直观的动态规划算法过于低效、直观的动态规划算法过于低效p 在这个时候，巧妙的使用贪心思想，将其融入在这个时候，巧妙的使用贪心思想，将其融入到动态规划中，动态规划便焕发出了新的光彩到动态规划中，动态规划便焕发出了新的光彩状态过于庞大第1页/共22页第二页，共23页。第2页/共22页第三页，共23页

2、。第3页/共22页第四页，共23页。第4页/共22页第五页，共23页。时间复杂(fz)度过大，无法满足要求田忌田忌齐王齐王2000-200第5页/共22页第六页，共23页。齐王最强的马田忌最强的马用田忌最差的马去输给齐王最强的马用田忌最差的马去输给齐王最强的马输给能赢用田忌最强的马去战胜用田忌最强的马去战胜(zhnshng)齐齐王最强的马王最强的马战平用田忌最强的马去打平齐王最强的马用田忌最强的马去打平齐王最强的马或者或者(huzh)用田忌最差的马去输给齐王最强的马用田忌最差的马去输给齐王最强的马第6页/共22页第七页，共23页。收益(shuy)为0收益(shuy)为200第7页/共22页第八

3、页，共23页。收益(shuy)为200收益(shuy)为0第8页/共22页第九页，共23页。igj,1- j1,-fii,1,j)-(i-gnj1,-maxfi jfi,O(n2)第9页/共22页第十页，共23页。第10页/共22页第十一页，共23页。第11页/共22页第十二页，共23页。树上的结点树上的结点(ji din)个数个数n最多为最多为1000，每，每个结点个结点(ji din)的分叉数的分叉数k最多为最多为8。第12页/共22页第十三页，共23页。(1+4+6)/3 = 11/3蜗牛从根结点蜗牛从根结点1 1出发开始寻找出发开始寻找(xnzho)(xnzho)它的房它的房子子它的房

4、子可能遗失在叶结点它的房子可能遗失在叶结点2 2、4 4、5 5上上在结点在结点3 3上住着一只虫子，它会告诉蜗牛，房子上住着一只虫子，它会告诉蜗牛，房子是否在以是否在以3 3为根的子树上为根的子树上这种走法没有充分发挥虫子在这里这种走法没有充分发挥虫子在这里(zhl)的的作用！作用！第13页/共22页第十四页，共23页。(3+2+4)/3 = 3Worm Said : No!Worm Said : Yes!第14页/共22页第十五页，共23页。 不难分析出本题是用树型动态规划来求解。 Fai表示蜗牛的房子在i为根的子树上的期望步数和 Fbi表示蜗牛的房子不在i为根的子树上的期望步数和（也就是

5、遍历该子树需要的时间，如果i处有虫子(chng zi)，那么Fbi=0） 用Leavesi 表示i为根的子树上叶子节点的数目。 问题的解答就是Fa根结点/Leaves根结点。如果结点如果结点u u有有k k个儿子个儿子, ,我们按照我们按照(nzho)S1.Sk(nzho)S1.Sk进行访问，进行访问，FauFau的计算方式的计算方式是：是：Fau = 0; Fbu = 0;Fau = 0; Fbu = 0;for i = 1 for i = 1 to to k do k dobeginbegin Fau = Fau + (Fbu + 1) Fau = Fau + (Fbu + 1) Leav

6、esSi + LeavesSi + FaSi;FaSi; Fbu = Fbu + FbSi + 2; Fbu = Fbu + FbSi + 2;end;end; kiijiijSFaSLeavesSFbuFa111) ) 1)2(Fbu的值与访问的值与访问(fngwn)顺序无关顺序无关第15页/共22页第十六页，共23页。第16页/共22页第十七页，共23页。另一个结论：如果另一个结论：如果A一定一定(ydng)放在放在B前，前，B一定一定(ydng)放在放在C前，可以推导出前，可以推导出A一定一定(ydng)放在放在C前。前。O(nklog2k)12kvv+1。 运用贪心(tnxn)思想分析

7、问题u)2()2(11vvvvSLeavesSFbSLeavesSFb元素之间存在可比性，且可比元素之间存在可比性，且可比性存在着传递性，因此可以确性存在着传递性，因此可以确定出一个全序关系定出一个全序关系此时此时FaS1.k和和FbS1.k的值都已知，的值都已知，Fau的值待定的值待定我们考虑一种访问顺序中的两个相邻元素我们考虑一种访问顺序中的两个相邻元素v和和v+1第17页/共22页第十八页，共23页。第18页/共22页第十九页，共23页。确立确立(qul)状状态态优化算法优化算法合理的运用题目中隐含的合理的运用题目中隐含的特殊信息特殊信息第19页/共22页第二十页，共23页。勇于探索大胆(ddn)创新举一反三(j y fn sn)第20页/共22页第二十一页，共23页。第21页/共22页第二十二页，共23页。NoImage内容(nirng)总结会计学。而在实际的解题过程中，状态信息往往是隐含(yn hn)的。第3页/共22页。这个问题很显然可以转化成一个二分图最佳匹配的问题。蜗牛从根结点出发开始寻找它遗失在某个叶子结点的房子。它的房子可能遗失在叶结点