《动态规划2课件.ppt》由会员分享，可在线阅读，更多相关《动态规划2课件.ppt（37页珍藏版）》请在三一文库上搜索。
1、漆 氖 琼 吧 船 鲁 韩 钝 延 急 柿 苟 昆 霞 盆 吊 烈 释 匡 曙 萧 痢 盎 八 翌 父 枉 啥 良 庇 卞 勇 动 态 规 划 2 课 件 动 态 规 划 2 课 件 ACM 程序设计 计算机学院 刘春英 诀 阀 腋 挽 赃 漓 慕 卞 息 蚁 足 滩 厩 价 亿 漓 徽 序 党 承 夫 虑 泪 七 雄 郑 钠 沦 浮 颂 宅 占 动 态 规 划 2 课 件 动 态 规 划 2 课 件 * 1 今天，今天， 你 了吗？ AC 诬 均 娟 舟 朽 器 弯 甜 临 弊 拜 距 蔓 骚 臻 桑 近 核 池 惩 揖 鄙 未 荫 汇 溪 弘 经 衡 虑 掉 衰 动 态 规 划 2 课 件
2、 动 态 规 划 2 课 件 Date 2 每周一星（每周一星（4 4）：）： 我爱小芳 币 氰 凉 务 恼 蹄 萨 庸 抽 隙 仔 斡 黔 放 瘁 近 升 糠 全 溃 征 卿 尺 目 系 济 乘 残 夕 毒 材 皖 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 3 第五讲第五讲 动态规划(2) （Dynamic programming） 种 捂 骡 浮 游 筷 苑 脯 崩 零 契 堆 尤 豹 鞋 夕 拽 彼 殴 庄 瘸 痉 篷 即 橱 勉 疾 惜 糠 窑 尸 歌 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 4 一、一、HDOJ_HDOJ_1421 1
3、421 搬寝室搬寝室 Sample Input 2 1 1 3 Sample Output 4 丝 巷 歌 顷 焦 绰 砒 祝 搭 绑 嫂 坞 稽 布 历 猛 字 拼 参 袄 姐 兢 呈 盘 侯 震 纯 蒂 掐 贫 私 颗 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 5 第一感觉：第一感觉： l根据题目的要求，每次提的两个物品重 量差越小越好，是不是每次提的物品一 定是重量相邻的物品呢？ l证明：假设四个从小到大的数：a、b、c 、d，只需证明以下表达式成立即可： l(a-b)2+(c-d)2(a-c)2+(b-d)2 l(a-b)2+(c-d)2=2k） 妖 膀 话 浙
4、 短 莆 愚 链 尿 永 籍 聋 对 充 照 老 桓 摔 藕 逸 函 戏 师 抗 狗 虏 型 吴 痞 替 炒 污 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 9 本题算法(略)： l哪位同学做个陈述？ 俩 荡 扫 纠 郭 创 譬 独 粹 真 潜 诽 无 搬 谋 喘 丰 小 琅 奶 帆 家 霸 诞 胁 饮 潭 藕 葬 蔓 册 笑 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 10 二、二、HDOJ_1058 HDOJ_1058 Humble NumbersHumble Numbers Problem Description A number whose
5、only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, . shows the first 20 humble numbers. Write a program to find and print the nth element in this sequence 规 曹 呸 升 捐 沪 栅 馒 闰 酋 钧 颖 泽 抡 摘 种 烽 美 囚 檄 评 袄 贰 奇 确 顺
6、 橡 潞 阴 踢 珐 焙 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 11 思考：思考： 动态规划的特征体现在什么动态规划的特征体现在什么 地方？地方？ 剩 伟 颁 古 泡 吊 鲍 吏 涩 贴 瓶 冀 世 费 染 月 目 悦 巡 茎 坎 栓 舟 谢 崭 届 溺 剂 趟 泥 你 味 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 12 算法分析：典型的算法分析：典型的DP!DP! l1-? l1-2=min(1*2,1*3,1*5,1*7) l1-2-3=min(2*2,1*3,1*5,1*7) l1-2-3-4=min(2*2,2*3,1*5,1*7)
7、l1-2-3-4-5=min(3*2,2*3,1*5,1*7) 波 奋 制 烁 胺 钞 讲 华 讹 免 吹 祟 摸 猛 骗 匹 勘 坟 诣 伙 拼 分 抠 久 乌 欠 通 酿 柯 迭 源 蓑 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 13 状态转移方程？状态转移方程？ lF(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7 ) (ni,j,k,m) 特别的： i,j,k,m 只有在本项被选中后才移动 各 昨 乘 夷 搽 歌 先 蠢 箩 浆 猛 豆 炙 澡 屯 彰 兆 谗 腋 撑 券 梁 佑 磊 都 捌 幕 隋 湾 哲 譬 韶 动 态 规 划 2 课
8、件 动 态 规 划 2 课 件 Date 14 三、经典问题三、经典问题 最短路径问题最短路径问题 V0 V1 V2 V3 V4 V5 100 10 30 10 5 50 20 60 起 点 终 点 最短 路径 路径 长度 V0 V1无 V2（V0,V2）10 V3(V0,V4,V3)50 V4(V0,V4)30 V5(V0,V4,V3,V5 ) 60 袖 影 片 芥 乘 迹 衷 昨 煎 帚 篱 峡 嫉 骡 东 瘴 兼 盘 雌 吠 扎 蠢 派 季 造 舅 悼 窑 照 依 瘦 泣 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 15 求源点到终点的最短路径的算法 的基本思想:
9、按照最短路径的长度递增的 次序依次求得源点到其余各点的 最短路径。 茵 写 讲 麓 曲 牧 滨 可 奔 鞘 掠 亦 粤 董 妓 岩 鸟 坤 痰 糊 许 显 卫 笋 拘 裙 么 稻 汁 弧 傲 援 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 16 在这条路径上，必定只含一条弧，并且 这条弧的权值最小。 路径长度最短的最短路径的特点： 假设，从源点到顶点V1的最短路径 是所有最短路径中长度最短者。 待 巡 昧 添 摆 溶 涂 幼 删 想 阎 凹 酞 藏 怨 滞 赞 离 醚 俊 须 刽 切 戚 逛 俱 偏 辉 钟 履 滑 予 动 态 规 划 2 课 件 动 态 规 划 2 课
10、件 Date 17 下一条路径长度次短的最短路径的特 点： 它只可能有两种情况：或者是直接 从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达 该顶点(由两条弧组成)。 十 泰 垣 抄 贞 爪 江 檀 徘 匠 愿 造 掘 漾 炳 锑 游 顾 贤 铜 傻 侮 捶 割 迅 殷 香 哑 各 亭 画 躇 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 18 再下一条路径长度次短的路径特点: 它可能有三种情况：或者是直接从源 点到该点(只含一条弧)；或者是从源点 经过顶点v1，再到达该顶点(由两条弧组 成)；或者是从源点经过顶点v2，再到达 该顶点。 簿 娥 怨 隶 实 漆
11、 铆 爽 伞 措 殿 圆 深 蛤 外 倚 碉 天 材 灾 徐 刚 动 冤 冠 亢 凹 戏 例 辅 敝 键 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 19 其余最短路径的特点： 它或者是直接从源点到该点(只含一条 弧)；或者是从源点经过已求得最短路 径的顶点，再到达该顶点。 人 糖 孝 袄 滴 檀 章 哦 惫 簇 坝 蔑 播 棕 吝 惦 榜 没 玫 臼 烦 氨 峡 蝴 硒 四 愁 莽 烛 剧 蹦 犹 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 20 求最短路径的迪杰斯特拉算法： 0）准备工作： 设置辅助数组Dist，其中每个分量 Distk表示：当前
12、所求得的从源点到 其余各顶点k的最短路径。 茎 戚 馏 补 吃 至 攘 蓖 原 森 钾 蔑 碧 咯 娥 殴 梅 釜 呛 拭 片 吠 剿 颧 斟 鄂 毡 书 棋 塞 蔓 撤 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 21 1）在所有从源点出发的弧中选取一条权 值最小的弧，即为第一条最短路径。 V0和k之间存在弧 V0和k之间不存在弧 其中的最小值即为最短路径的长度。 般 雅 跌 盂 煤 撇 愧 淖 牙 凳 受 季 剖 膨 梳 迂 冰 论 确 眨 言 肋 任 居 梗 诞 艳 颇 恳 锈 竣 蛛 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 22 2）修改
13、其它各顶点的Distk值。 (为什么？) 具体操作：假设求得最短路径的顶点为 u，若 Distu+G.arcsukDistk 则将Distk改为Distu+G.arcsuk。 奎 低 鹏 字 揩 乾 皋 泰 场 奢 歧 文 京 恭 婪 深 擒 惠 紧 卓 币 弯 菜 跺 彦 让 靠 管 搁 此 述 矾 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 23 3）选出下一条最短路径，重复以上 操作，直到求出所有的最短路径。 搞定！ 说明:求两点之间的最短路径和 求一个点到其余所有点的最短路 径工作量一样。 妈 胖 晶 纬 凹 扦 抓 荐 招 贯 珊 凉 擂 琳 嫌 水 截 菇 载
14、 捐 灼 僵 筒 砂 鲁 暖 氏 懦 蓟 躲 刹 牢 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 24 练习：模拟求最短路径练习：模拟求最短路径 终点 从 V0到各终点的D值 i=1i=2i=3i=4i=5 V1 V210 V3 V430 V5100 VjV2 V0 V1 V2 V3 V4 V5 100 10 30 10 5 50 20 60 胰 鞋 镊 滔 吁 彬 宁 阐 邢 侄 荣 盔 韭 抄 挂 急 蒜 吵 硒 烤 惕 缓 萤 瑰 国 拨 陵 母 滨 委 炎 郝 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 25 练习：模拟求最短路径练习：模拟求
15、最短路径 V0 V1 V2 V3 V4 V5 终点 从 V0到各终点的D值 i=1i=2i=3i=4i=5 V1 V210 V36050 V43030 V51001009060 VjV2V4V3V5 侧 痔 矽 沁 踪 总 临 铜 山 钨 瓶 粥 企 坎 黍 险 丫 稠 喇 莉 柒 喧 蓉 掺 股 罕 饿 宙 碳 贼 婆 矮 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 26 回顾原图：最短路径问题回顾原图：最短路径问题 V0 V1 V2 V3 V4 V5 100 10 30 10 5 50 20 60 起 点 终 点 最短 路径 路径 长度 V0 V1无 V2（V0,V2
16、）10 V3(V0,V4,V3)50 V4(V0,V4)30 V5(V0,V4,V3,V5 ) 60 球 讽 玉 肤 窜 酿 棘 埠 得 蛹 赂 亡 佛 厄 抖 铆 镍 省 郧 雅 尾 侦 哼 睁 严 疤 他 恿 岛 搔 丝 挑 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 27 思考题：思考题： 1074_DoingHomework 烷 裤 甫 蔡 芜 泼 煞 茎 啮 悄 撰 议 罢 逝 肃 培 捞 奖 宫 丑 敷 憋 幅 烫 刺 囤 蹬 冠 在 溯 窟 熄 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 28 思考：如何自顶向下的分析？ ？ 刁 瞻 颖
17、 信 砚 藩 并 僻 殉 坏 啮 牛 告 痕 辽 靡 锄 叹 籽 气 赎 仙 府 碰 臂 铣 空 堑 谨 瞻 圆 峙 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 29 思考：如何自底向上的计算？ ？ 皋 艾 几 步 陕 棋 但 楔 仿 庆 杉 涤 课 拽 乔 巴 信 刚 等 请 葡 疲 醉 扯 大 终 劝 西 耐 皖 湖 痰 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 30 图示说明（假设有3门功课）： 123 1,22,31,3 1,2,3 僵 枣 庸 臻 坞 巩 态 乓 胯 咒 了 疫 山 边 碎 恼 下 缩 致 斤 粘 享 在 放 盏 裂 炳
18、萧 狗 匙 富 除 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 31 图示说明（假设有4门功课）： 1234 1,22,31,31,42,43,4 1,2,31,2,41,3,4 2,3,4 1,2,3,4 横 久 凛 疲 拉 戏 圣 停 催 吞 健 年 齐 抒 鸿 容 挫 诺 诡 栈 汕 歹 赣 副 莽 略 袍 珊 蹲 陷 醉 无 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 32 图示说明（假设有4门功课）： 1234 1,22,31,31,42,43,4 1,2,31,2,41,3,4 2,3,4 1,2,3,4 漠 雕 囊 匣 趟 续 盂 扦
19、葡 覆 户 聪 逗 策 奔 缄 伤 喀 烂 庶 槐 雪 箱 驹 卒 澄 勺 绞 陛 硕 卢 荷 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 33 象不象 数塔？ 钉 皇 挂 沙 迅 袁 耿 怂 匝 屎 割 郸 代 拌 松 冒 郧 砧 厉 纪 大 势 识 福 崭 晋 慢 缚 远 交 捏 钠 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 34 附录：附录：DPDP练习题练习题(HDOJ)(HDOJ)： l1003、1074、1087、1159、1160、1176 l1024、1025、1058、1069、1081 l1157、1158、1466 l1078
20、、1080、1114 l1203、1294、1227、1223 l1500、1501、1502、1503 l1505、1506、1510、2059 l最短路径：1142、1385、1548 玩 革 厨 饼 覆 读 舵 矿 汀 猩 从 跳 汾 也 牵 锥 竟 戍 泵 闸 噶 位 疡 栋 烟 畔 博 淮 焙 赏 仇 勘 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 35 下次课内容：下次课内容： 贪心算法 嘿 您 貌 蓉 月 棘 患 厢 逸 蟹 赡 货 车 尸 密 千 詹 奠 焚 奋 澳 疮 陈 槛 埂 燃 笺 属 假 夜 盼 臣 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 36 See you next week.See you next week. Thank you! 隙 藩 饵 母 掳 腹 画 绣 渔 游 被 味 鸥 弥 网 从 豁 掘 抖 喂 寐 询 门 炔 协 娟 勤 合 命 契 鸣 囊 动 态 规 划 2 课 件 动 态 规 划 2 课 件 Date 37