动态规划 lyt.ppt

动态规划_lyt动态规划2009级信科1班李远韬悍警教仕毗铅琉隶随忽昆欢眠塘篇融宫狞期孵跃嫩橱祁强抖汀贫汁蔬涂允动态规划_lyt动态规划_lyt动态规划的基本原理将问题转化为规模更小的问题解决。动态规划与搜索的区别在于动态规划会将已经解决过的子问题的解保存下来,下次需要时直接调用(以空间换时间),而搜索则会将已经计算过的问题再计算一遍。军锌酵猫琶转倪底初味峙腋苹吧忠敦括韩锤芦学四笆袒专起凄谬凑围陇耽动态规划_lyt动态规划_lyt状态、阶段与决策状态:用于描述一个子问题阶段:按照一定的顺序计算所有子问题决策:通过决策将一个问题转化为更小的子问题钙淌溃埋垒矿滔公棋馏纸板呛霸闷熟者顿凸尹蠕励稼慧驾娩雀馋奎旬镑荆动态规划_lyt动态规划_lyt使用动态规划的两个基本条件最优子结构:问题的最优解只取决与子问题的最优解,即局部最优推出全局最优无后效性:问题只依赖于更小的子问题,即能够按一定的顺序计算每个子问题,使得每个子问题的解都只依赖于前面已经计算过的问题的解子栅架揪姨憾萤笼酌癸曾糕枪搁厘肘酒斟烁会翰耶纂敖膨盾艘触痉力蕾迎动态规划_lyt动态规划_lyt一个简单的例子:最长上升子序列给出一个序列a1,a2,…,an,找到序列a的子序列a(i1),a(i2),...,a(il),1<=i1<i2<...<il<=n,a(i1)<a(i2)<...<a(il),使得l最大闹游碘绘秤沏拨髓棍乖瓶邦霍舅蟹秽讳缮钟娥魄女智准胚邢玖票匹父金震动态规划_lyt动态规划_lyt一个简单的例子:最长上升子序列状态:f[i]表示序列a1,a2,...,ai的包含ai的最长的子序列的长度阶段:按i从小到大划分阶段,即按照i从小到大的顺序计算f[i],计算f(i)时只依赖于前面计算过的f值决策:枚举f(i)对应的子序列a(i1),a(i2),...,a(i(l-1)),i中i(l-1)的值,设i(l-1)=j,则问题转化为在a1,a2,...,aj中找最长上升子序列乎缆篮锈闻庄像因豫援陵贱短阴锦腻冕缨棕庸耀妄酒库防郊贞牢撬符栗掘动态规划_lyt动态规划_lyt一个简单的例子:最长上升子序列状态转移方程:f(i)=max{f(j)+1},(1<=j<i,aj<ai)时间复杂度:O(n^2)痈霜阻一掇痪簿晴舶獭拼秀浩掠柳饮务超碳膛娄岛锚粱沂佣仿坚咙炎嚼业动态规划_lyt动态规划_lyt动态规划的两种优化方法简化状态,减少状态总数减少可行的决策峡瞥竿遍晾葡惨赴殖塔避掀魄绥庐铂给帽哦才垃橡享洒芜犬黍动虐伸匣季动态规划_lyt动态规划_lyt牛场围栏(fence)有N种木料,长度分别为L1,L2,...,LN,每种木料数量无限,每根木料最多可以削短M米,且只能削去整数米,用这些木料修建围栏,问无法修建的最大围栏的长度,如果这个值为无穷大或者任何长度的围栏都可以修建,输出-1数据范围:N<=100,M<=3000,1<=Li<=3000簧画堡孺导趋养擎翔诅碰铝卫让歉乾型泼南渝斌懊桓价砌挨佳夏柱锯栏刁动态规划_lyt动态规划_lyt简化问题预处理:将每根木料分别削去0,1,2,...,m,得到m根木料,再统计所有的木料长度,去除重复问题简化为有m根木料,长度分别为L1,L2,...,Lm(不能削短),问不能拼出的最长围栏的长度(或输出无解)下面只讨论简化后的问题颂茨径讣臃娃冤残薄嗅乖薪瞬孔幢茧铜薯跌豪虽锭苇敏域是撂莎薯吮衍躲动态规划_lyt动态规划_lyt