动态规划 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