C案例04动态规划.ppt

2020 4 16 1 第四讲 动态规划 Dynamicprogramming 2020 4 16 2 一 经典问题 数塔问题 有形如下图所示的数塔 从顶部出发 在每一结点可以选择向左走或是向右走 一直走到底层 要求找出一条路径 使路径上的值最大 2020 4 16 3 用暴力的方法 可以吗 2020 4 16 4 这道题如果用枚举法 暴力思想 在数塔层数稍大的情况下 如31 则需要列举出的路径条数将是一个非常庞大的数目 2 30 1024 3 10 9 10亿 试想一下 2020 4 16 5 拒绝暴力 倡导和谐 2020 4 16 6 从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值 只要左右两道路径上的最大值求出来了才能作出决策 同样 下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策 这样一层一层推下去 直到倒数第二层时就非常明了 如数字2 只要选择它下面较大值的结点19前进就可以了 所以实际求解时 可从底层开始 层层递进 最后得到最大值 结论 自顶向下的分析 自底向上的计算 考虑一下 2020 4 16 7 思路 从倒数第二行起 按照状态转移方程dp i j max dp i 1 j dp i 1 j 1 val i j 向上递推 直到val 1 1 此时dp 1 1 就是结果 2020 4 16 8 二 经典问题 最长有序子序列 问题描述 找出由n个元素组成的序列的最长有序子序列长度及其中一个最长有序子序列 注 这里有序指非递减顺序 且不要求子序列连续 例如 对于序列 3 7 1 5 9 3 其中最长有序子序列长度为3 这样的子序列有 3 7 9 1 5 9 3 5 9 2020 4 16 9 二 经典问题 最长有序子序列 2020 4 16 10 二 经典问题 最长有序子序列 2020 4 16 11 二 经典问题 最长有序子序列 2020 4 16 12 三1160FatMouse sSpeed ProblemDescriptionFatMousebelievesthatthefatteramouseis thefasteritruns Todisprovethis youwanttotakethedataonacollectionofmiceandputaslargeasubsetofthisdataaspossibleintoasequencesothattheweightsareincreasing butthespeedsaredecreasing InputInputcontainsdataforabunchofmice onemouseperline terminatedbyendoffile Thedataforaparticularmousewillconsistofapairofintegers thefirstrepresentingitssizeingramsandthesecondrepresentingitsspeedincentimeterspersecond Bothintegersarebetween1and10000 Thedataineachtestcasewillcontaininformationforatmost1000mice Twomicemayhavethesameweight thesamespeed oreventhesameweightandspeed 2020 4 16 13 三1160FatMouse sSpeed OutputYourprogramshouldoutputasequenceoflinesofdata thefirstlineshouldcontainanumbern theremainingnlinesshouldeachcontainasinglepositiveinteger eachonerepresentingamouse Ifthesenintegersarem 1 m 2 m n thenitmustbethecasethatW m 1 S m 2 S m n Inorderfortheanswertobecorrect nshouldbeaslargeaspossible Allinequalitiesarestrict weightsmustbestrictlyincreasing andspeedsmustbestrictlydecreasing Theremaybemanycorrectoutputsforagiveninput yourprogramonlyneedstofindone 2020 4 16 14 三1160FatMouse sSpeed SampleInput60081300600021005002000100040001100300060002000800014006000120020001900 SampleOutput44597 2020 4 16 15 三1160FatMouse sSpeed 解题思路 题目要求找到的体重递增 速度递减老鼠 先把老鼠的体重进行升序排序然后算出速度的最长递减子序列 2020 4 16 16 四1087SuperJumping Jumping Juping ProblemDescriptionNowadays akindofchessgamecalled SuperJumping Jumping Jumping isverypopularinHDU Maybeyouareagoodboy andknowlittleaboutthisgame soIintroduceittoyounow Thegamecanbeplayedbytwoormorethantwoplayers Itconsistsofachessboard 棋盘 andsomechessmen 棋子 andallchessmenaremarkedbyapositiveintegeror start or end Theplayerstartsfromstart pointandmustjumpsintoend pointfinally Inthecourseofjumping theplayerwillvisitthechessmeninthepath buteveryonemustjumpsfromonechessmantoanotherabsolutelybigger youcanassumestart pointisaminimumandend pointisamaximum Andallplayerscannotgobackwards Onejumpingcangofromachessmantonext alsocangoacrossmanychessmen andevenyoucanstraightlygettoend pointfromstart point Ofcourseyougetzeropointinthissituation Aplayerisawinnerifandonlyifhecangetabiggerscoreaccordingtohisjumpingsolution Notethatyourscorecomesfromthesumofvalueonthechessmeninyoujumpingpath Yourtaskistooutputthemaximumvalueaccordingtothegivenchessmenlist 2020 4 16 17 四1087SuperJumping Jumping Juping InputInputcontainsmultipletestcases Eachtestcaseisdescribedinalineasfollow Nvalue 1value 2 value NItisguarantiedthatNisnotmorethan1000andallvalue iareintherangeof32 int Atestcasestartingwith0terminatestheinputandthistestcaseisnottobeprocessed OutputForeachcase printthemaximumaccordingtorules andonelineonecase 2020 4 16 18 四1087SuperJumping Jumping Juping SampleInput313241234433210SampleOutput4103 解题思路 找序列中最大升序子序列的和 2020 4 16 20 动态规划算法与分治法类似 其基本思想也是将待求解问题分解成若干个子问题 算法总体思想 2020 4 16 21 但是经分解得到的子问题往往不是互相独立的 不同子问题的数目常常只有多项式量级 在用分治法求解时 有些子问题被重复计算了许多次 算法总体思想 2020 4 16 22 如果能够保存已解决的子问题的答案 而在需要时再找出已求得的答案 就可以避免大量重复计算 从而得到多项式时间算法 算法总体思想 T n 2020 4 16 23 动态规划基本步骤 找出最优解的性质 并刻划其结构特征 递归地定义最优值 以自底向上的方式计算出最优值 根据计算最优值时得到的信息 构造最优解 2020 4 16 24 动态规划算法的基本要素 一 最优子结构 问题的最优解包含着其子问题的最优解 这种性质称为最优子结构性质 在分析问题的最优子结构性质时 所用的方法具有普遍性 首先假设由问题的最优解导出的子问题的解不是最优的 然后再设法说明在这个假设下可构造出比原问题最优解更好的解 从而导致矛盾 利用问题的最优子结构性质 以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解 最优子结构是问题能用动态规划算法求解的前提 同一个问题可以有多种方式刻划它的最优子结构 有些表示方法的求解速度更快 空间占用小 问题的维度低 2020 4 16 25 动态规划算法的基本要素 二 重叠子问题 递归算法求解问题时 每次产生的子问题并不总是新问题 有些子问题被反复计算多次 这种性质称为子问题的重叠性质 动态规划算法 对每一个子问题只解一次 而后将其解保存在一个表格中 当再次需要解此子问题时 只是简单地用常数时间查看一下结果 通常不同的子问题个数随问题的大小呈多项式增长 因此用动态规划算法只需要多项式时间 从而获得较高的解题效率 2020 4 16 26 动态规划算法的基本要素 三 备忘录方法 备忘录方法的控制结构与直接递归方法的控制结构相同 区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看 避免了相同子问题的重复求解 intLookupChain inti intj if m i j 0 returnm i j if i j return0 intu LookupChain i i LookupChain i 1 j p i 1 p i p j s i j i for intk i 1 k j k intt LookupChain i k LookupChain k 1 j p i 1 p k p j if t u u t s i j k m i j u returnu 2020 4 16 27 五 经典问题 最长公共子序列 ProblemDescriptionAsubsequenceofagivensequenceisthegivensequencewithsomeelements possiblenone leftout GivenasequenceX anothersequenceZ isasubsequenceofXifthereexistsastrictlyincreasingsequenceofindicesofXsuchthatforallj 1 2 k xij zj Forexample Z isasubsequenceofX withindexsequence GiventwosequencesXandYtheproblemistofindthelengthofthemaximum lengthcommonsubsequenceofXandY Theprograminputisfromatextfile Eachdatasetinthefilecontainstwostringsrepresentingthegivensequences Thesequencesareseparatedbyanynumberofwhitespaces Theinputdataarecorrect Foreachsetofdatatheprogramprintsonthestandardoutputthelengthofthemaximum lengthcommonsubsequencefromthebeginningofaseparateline 2020 4 16 28 五 经典问题 最长公共子序列 HDOJ 1159 SampleInputabcfbcabfcabprogrammingcontestabcdmnp SampleOutput420 2020 4 16 29 最长公共子序列 若给定序列X x1 x2 xm 则另一序列Z z1 z2 zk 是X的子序列是指存在一个严格递增下标序列 i1 i2 ik 使得对于所有j 1 2 k有 zj xij 例如 序列Z B C D B 是序列X A B C B D A B 的子序列 相应的递增下标序列为 2 3 5 7 给定2个序列X和Y 当另一序列Z既是X的子序列又是Y的子序列时 称Z是序列X和Y的公共子序列 给定2个序列X x1 x2 xm 和Y y1 y2 yn 找出X和Y的最长公共子序列 2020 4 16 30 最长公共子序列的结构 设序列X x1 x2 xm 和Y y1 y2 yn 的最长公共子序列为Z z1 z2 zk 则 1 若xm yn 则zk xm yn 且zk 1是xm 1和yn 1的最长公共子序列 2 若xm yn且zk xm 则Z是xm 1和Y的最长公共子序列 3 若xm yn且zk yn 则Z是X和yn 1的最长公共子序列 由此可见 2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列 因此 最长公共子序列问题具有最优子结构性质 2020 4 16 31 子问题的递归结构 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系 用c i j 记录序列和的最长公共子序列的长度 其中 Xi x1 x2 xi Yj y1 y2 yj 当i 0或j 0时 空序列是Xi和Yj的最长公共子序列 故此时C i j 0 其它情况下 由最优子结构性质可建立递归关系如下 2020 4 16 32 辅助空间变化示意图 2020 4 16 33 计算最优值 由于在所考虑的子问题空间中 总共有 mn 个不同的子问题 因此 用动态规划算法自底向上地计算最优值能提高算法的效率 voidLCSLength intm intn char x char y int c int b inti j for i 1 i c i j 1 c i j c i 1 j b i j 2 else c i j c i j 1 b i j 3 构造最长公共子序列voidLCS inti intj char x int b if i 0 j 0 return if b i j 1 LCS i 1 j 1 x b cout x i elseif b i j 2 LCS i 1 j x b elseLCS i j 1 x b 2020 4 16 34 算法的改进 在算法lcsLength和lcs中 可进一步将数组b省去 事实上 数组元素c i j 的值仅由c i 1 j 1 c i 1 j 和c i j 1 这3个数组元素的值所确定 对于给定的数组元素c i j 可以不借助于数组b而仅借助于c本身在时间内确定c i j 的值是由c i 1 j 1 c i 1 j 和c i j 1 中哪一个值所确定的 如果只需要计算最长公共子序列的长度 则算法的空间需求可大大减少 事实上 在计算c i j 时 只用到数组c的第i行和第i 1行 因此 用2行的数组空间就可以计算出最长公共子序列的长度 进一步的分析还可将空间需求减至O min m n 2020 4 16 35 六 经典问题 1421搬寝室 ProblemDescription搬寝室是很累的 xhd深有体会 时间追述2006年7月9号 那天xhd迫于无奈要从27号楼搬到3号楼 因为10号要封楼了 看着寝室里的n件物品 xhd开始发呆 因为n是一个小于2000的整数 实在是太多了 于是xhd决定随便搬2 k件过去就行了 但还是会很累 因为2 k也不小是一个不大于n的整数 幸运的是xhd根据多年的搬东西的经验发现每搬一次的疲劳度是和左右手的物品的重量差的平方成正比 这里补充一句 xhd每次搬两件东西 左手一件右手一件 例如xhd左手拿重量为3的物品 右手拿重量为6的物品 则他搬完这次的疲劳度为 6 3 2 9 现在可怜的xhd希望知道搬完这2 k件物品后的最佳状态是怎样的 也就是最低的疲劳度 请告诉他吧 2020 4 16 36 六 经典问题 1421搬寝室 Input每组输入数据有两行 第一行有两个数n k 2 2 k n 2000 第二行有n个整数分别表示n件物品的重量 重量是一个小于2 15的正整数 Output对应每组输入数据 输出数据只有一个表示他的最少的疲劳度 每个一行 2020 4 16 37 六 经典问题 1421搬寝室 SampleInput2113SampleOutput4 2020 4 16 38 第一感觉 根据题目的要求 每次提的两个物品重量差越小越好 是不是每次提的物品一定是重量相邻的物品呢 证明 假设四个从小到大的数 a b c d 只需证明以下表达式成立即可 a b 2 c d 2 a c 2 b d 2 a b 2 c d 2 a d 2 b c 2 略 2020 4 16 39 预备工作 排序 2020 4 16 40 第二感觉 对于一次操作 显然提的物品重量越接近越好 是不是可以贪心呢 请思考 考虑以下情况 1458 什么结论 2020 4 16 41 详细分析 从最简单的情况考虑 2个物品选一对 结论显然 结论 4个物品选一对 如何利用前面的知识 3个物品选一对 n个物品选一对 最终问题 n个物品选k对 n 2k 如何 n个物品选二对 2020 4 16 42 解题思路 先对物品的重量进行排序 取相邻的物品 将相邻的物品的差的平方另外存储 得到状态转移方程 dp i j min dp i 1 j dp i 2 j 1 s i s i 是代表i i 1这两个物品的疲惫度 因为s i 1 s i 代表的是ai 1 ai ai 1的疲惫度 中间共享了一个ai 所以第二项要用dp i 2 2020 4 16 43 参考代码 include includeusingnamespacestd defineINF0 x7fffffffintdp 2000 2000 a 2000 s 2000 intmain intn k i j while scanf d d 2020 4 16 44 七 经典问题 1058HumbleNumbers ProblemDescriptionAnumberwhoseonlyprimefactorsare2 3 5or7iscalledahumblenumber Thesequence1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 showsthefirst20humblenumbers Writeaprogramtofindandprintthenthelementinthissequence 2020 4 16 45 七 经典问题 1058HumbleNumbers InputTheinputconsistsofoneormoretestcases Eachtestcaseconsistsofoneintegernwith1 n 5842 Inputisterminatedbyavalueofzero 0 forn OutputForeachtestcase printonelinesaying Thenthhumblenumberisnumber Dependingonthevalueofn thecorrectsuffix st nd rd or th fortheordinalnumbernthhastobeusedlikeitisshowninthesampleoutput 2020 4 16 46 七 经典问题 1058HumbleNumbers 2020 4 16 47 算法分析 典型的DP 1 1 2 min 1 2 1 3 1 5 1 7 1 2 3 min 2 2 1 3 1 5 1 7 1 2 3 4 min 2 2 2 3 1 5 1 7 1 2 3 4 5 min 3 2 2 3 1 5 1 7 2020 4 16 48 状态转移方程 F n min F i 2 F j 3 F k 5 F m 7 n i j k m 特别的 i j k m只有在本项被选中后才移动 2020 4 16 49 关键问题 这个题目的哪些经验值得我们借鉴 2020 4 16 50 八免费馅饼1176 2020 4 16 51 八免费馅饼1176 ProblemDescription都说天上不会掉馅饼 但有一天gameboy正走在回家的小径上 忽然天上掉下大把大把的馅饼 说来gameboy的人品实在是太好了 这馅饼别处都不掉 就掉落在他身旁的10米范围内 馅饼如果掉在了地上当然就不能吃了 所以gameboy马上卸下身上的背包去接 但由于小径两侧都不能站人 所以他只能在小径上接 由于gameboy平时老呆在房间里玩游戏 虽然在游戏中是个身手敏捷的高手 但在现实中运动神经特别迟钝 每秒种只有在移动不超过一米的范围内接住坠落的馅饼 现在给这条小径如图标上坐标 为了使问题简化 假设在接下来的一段时间里 馅饼都掉落在0 10这11个位置 开始时gameboy站在5这个位置 因此在第一秒 他只能接到4 5 6这三个位置中其中一个位置上的馅饼 问gameboy最多可能接到多少个馅饼 假设他的背包可以容纳无穷多个馅饼 2020 4 16 52 八免费馅饼1176 Input输入数据有多组 每组数据的第一行为以正整数n 0 n 100000 表示有n个馅饼掉在这条小径上 在结下来的n行中 每行有两个整数x T 0 T 100000 表示在第T秒有一个馅饼掉在x点上 同一秒钟在同一点上可能掉下多个馅饼 n 0时输入结束 Output每一组输入数据对应一行输出 输出一个整数m 表示gameboy最多可能接到m个馅饼 提示 本题的输入数据量比较大 建议用scanf读入 用cin可能会超时 2020 4 16 53 八免费馅饼1176 SampleInput65141617272830SampleOutput4 2020 4 16 54 如何解决 请发表见解 2020 4 16 55 解题思路 有点类似于数塔 Dp t i MAX Dp t 1 i 1 Dp t 1 i Dp t 1 i 1 DATA t i 2020 4 16 56 自学题 请大家自学课本P239最短路径问题P247插入乘号问题 2020 4 16 57 如果各个子问题不是独立的 不同的子问题的个数只是多项式量级 如果我们能够保存已经解决的子问题的答案 而在需要的时候再找出已求得的答案 这样就可以避免大量的重复计算 由此而来的基本思路是 用一个表记录所有已解决的子问题的答案 不管该问题以后是否被用到 只要它被计算过 就将其结果填入表中 小结 DP的基本思想