资源描述：
《《动态规划课件》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ACM程序设计计算机学院刘春英6/29/20211今天，你了吗？AC6/29/20212每周一星（4）：我爱小芳6/29/20213第五讲动态规划(2)（Dynamicprogramming）6/29/20214一、HDOJ_1421搬寝室SampleInput21 13SampleOutput46/29/20215第一感觉：根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？证明：假设四个从小到大的数：a、b、c、d，只需证明以下表达式成立即可：(a-b)^2+(c-d)^2<(a-c
2、)^2+(b-d)^2(a-b)^2+(c-d)^2<(a-d)^2+(b-c)^2……(略)6/29/20216预备工作：排序！6/29/20217第二感觉：对于一次操作，显然提的物品重量越接近越好，是不是可以贪心呢？请思考…考虑以下情况：1458什么结论？6/29/20218详细分析：从最简单的情况考虑：2个物品选一对，结论显然结论？4个物品选一对？（如何利用前面的知识）3个物品选一对，…n个物品选一对，…最终问题：n个物品选k对，如何？（n>=2k）6/29/20219本题算法(略)：哪位同学做个陈述？6/29/202
3、110二、HDOJ_1058HumbleNumbersProblemDescriptionAnumberwhoseonlyprimefactorsare2,3,5or7iscalledahumblenumber.Thesequence1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,...showsthefirst20humblenumbers. Writeaprogramtofindandprintthenthelementinthissequence6/29/2021
4、11思考：动态规划的特征体现在什么地方？6/29/202112算法分析：典型的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)6/29/202113状态转移方程？F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7)(n>i,j,k,m)特别的：i,j,k,m只有在本项被选中后才移动6/29/202114三
5、、经典问题最短路径问题V0V1V2V3V4V51001030105502060起点终点最短路径路径长度V0V1无V2（V0,V2）10V3(V0,V4,V3)50V4(V0,V4)30V5(V0,V4,V3,V5)606/29/202115求源点到终点的最短路径的算法的基本思想::按照最短路径的长度递增的次序依次求得源点到其余各点的最短路径。…6/29/202116在这条路径上，必定只含一条弧，并且这条弧的权值最小。路径长度最短的最短路径的特点：假设，从源点到顶点V1的最短路径是所有最短路径中长度最短者。6/29/20211
6、7下一条路径长度次短的最短路径的特点：它只可能有两种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。6/29/202118再下一条路径长度次短的路径特点:它可能有三种情况：或者是直接从源点到该点(只含一条弧)；或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。6/29/202119其余最短路径的特点：它或者是直接从源点到该点(只含一条弧)；或者是从源点经过已求得最短路径的顶点，再到达该顶点。6/29/202120求最短路径的迪杰
7、斯特拉算法：0）准备工作：设置辅助数组Dist，其中每个分量Dist[k]表示：当前所求得的从源点到其余各顶点k的最短路径。6/29/2021211）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度。6/29/2021222）修改其它各顶点的Dist[k]值。(为什么？)具体操作：假设求得最短路径的顶点为u，若Dist[u]+G.arcs[u][k]8、21233）选出下一条最短路径，重复以上操作，直到求出所有的最短路径。搞定！！！说明:求两点之间的最短路径和求一个点到其余所有点的最短路径工作量一样。6/29/202124练习：模拟求最短路径终点从V0到各终点的D值i=1i=2i=3i=4i=5V1∞V210V3∞V430V5100VjV
