ACM 程序设计 计算机学院 刘春英 2019/5/23

今天， AC 你 了吗？ 2019/5/23

每周一星（4）： 我爱小芳 2019/5/23

第五讲 动态规划(2) （Dynamic programming） 2019/5/23

一、HDOJ_1421 搬寝室 Sample Input 2 1 1 3 Sample Output 4 2019/5/23

第一感觉： 根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？ 证明：假设四个从小到大的数：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 ……(略) 2019/5/23

预备工作： 排序！ 2019/5/23

第二感觉： 对于一次操作，显然提的物品重量越接近越好，是不是可以贪心呢？ 请思考… 考虑以下情况： 1 4 5 8 什么结论？ 1 4 5 8 什么结论？ 2019/5/23

详细分析： 从最简单的情况考虑： 2个物品选一对，结论显然 结论？ 3个物品选一对，… 4个物品选一对？（如何利用前面的知识） n个物品选一对，… 最终问题：n个物品选k对，如何？（n>=2k） 结论？ 2019/5/23

本题算法(略)： 哪位同学做个陈述？ 2019/5/23

二、HDOJ_1058 Humble Numbers Problem Description A number whose 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 2019/5/23

思考： 动态规划的特征体现在什么地方？ 2019/5/23

算法分析：典型的DP! 1 ->? 1 ->2=min(1*2,1*3,1*5,1*7) 2019/5/23

状态转移方程？ F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7) (n>i,j,k,m) 特别的： 2019/5/23

三、经典问题 最短路径问题 起点 终点 最短 路径 路径长度 V0 V1 无 V2 （V0,V2） 10 V3 (V0,V4,V3) 50 三、经典问题 最短路径问题 V0 V1 V2 V3 V4 V5 100 10 30 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 2019/5/23

求源点到终点的最短路径的算法的基本思想:: 按照最短路径的长度递增的次序依次求得源点到其余各点的最短路径。 … 2019/5/23

假设，从源点到顶点V1的最短路径是所有最短路径中长度最短者。 路径长度最短的最短路径的特点： 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 2019/5/23

它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 下一条路径长度次短的最短路径的特点： 它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。 2019/5/23

再下一条路径长度次短的路径特点: 它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。 2019/5/23

其余最短路径的特点： 它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。 2019/5/23

求最短路径的迪杰斯特拉算法： 0）准备工作： 设置辅助数组Dist，其中每个分量Dist[k] 表示：当前所求得的从源点到其余各顶点 k 的最短路径。 2019/5/23

1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。 V0和k之间存在弧 V0和k之间不存在弧 其中的最小值即为最短路径的长度。 2019/5/23

2）修改其它各顶点的Dist[k]值。 (为什么？) 具体操作：假设求得最短路径的顶点为u，若 Dist[u]+G.arcs[u][k]<Dist[k] 则将 Dist[k] 改为 Dist[u]+G.arcs[u][k]。 2019/5/23

搞定！！！ 说明:求两点之间的最短路径和求一个点到其余所有点的最短路径工作量一样。 3）选出下一条最短路径，重复以上操作，直到求出所有的最短路径。 搞定！！！ 说明:求两点之间的最短路径和求一个点到其余所有点的最短路径工作量一样。 2019/5/23

练习：模拟求最短路径 终点 从 V0到各终点的D值 i=1 i=2 i=3 i=4 i=5 V1 ∞ V2 10 V3 V4 30 V5 100 10 30 5 50 20 60 终点 从 V0到各终点的D值 i=1 i=2 i=3 i=4 i=5 V1 ∞ V2 10 V3 V4 30 V5 100 Vj 2019/5/23

练习：模拟求最短路径 终点 从 V0到各终点的D值 i=1 i=2 i=3 i=4 i=5 V1 ∞ V2 10 V3 60 50 V4 30 V5 100 90 Vj 2019/5/23

回顾原图：最短路径问题 起点 终点 最短 路径 路径长度 V0 V1 无 V2 （V0,V2） 10 V3 (V0,V4,V3) 50 V4 100 10 30 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 2019/5/23

思考题： 1074_Doing  Homework 2019/5/23

思考：如何自顶向下的分析？ ？ 2019/5/23

思考：如何自底向上的计算？ ？ 2019/5/23

图示说明（假设有3门功课）： 1 2 3 1,2 2,3 1,3 1,2,3 2019/5/23

图示说明（假设有4门功课）： 1,2,3,4 1,2,3 1,2,4 1,3,4 2,3,4 1,2 2,3 1,3 1,4 2,4 3,4 1 2 3 4 2019/5/23

图示说明（假设有4门功课）： 1,2,3,4 1,2,3 1,2,4 1,3,4 2,3,4 1,2 2,3 1,3 1,4 2,4 3,4 1 2 3 4 2019/5/23

象不象 数塔？ 2019/5/23

附录：DP练习题(HDOJ)： 1003、1074、1087、1159、1160、1176 1024、1025、1058、1069、1081 1157、1158、1466 1078、1080、1114 1203、1294、1227、1223 1500、1501、1502、1503 1505、1506、1510、2059 最短路径：1142 、1385 、1548 2019/5/23

下次课内容： 贪心算法 2019/5/23

Thank you! See you next week. 2019/5/23