动态规划2课件

1、2021-10-231acm acm 程序设计程序设计计算机学院计算机学院 刘春英刘春英2021-10-232你 了吗？ac2021-10-233我爱小芳 2021-10-234动态规划动态规划(2)（dynamic programming）2021-10-235sample input2 1 1 3sample output42021-10-236l根据题目的要求，每次提的两个物品重量差越小越好，是不是每次提的物品一定是重量相邻的物品呢？l证明：假设四个从小到大的数：a、b、c、d，只需证明以下表达式成立即可：l(a-b)2+(c-d)2 (a-c)2+(b-d)2l(a-b)2+(c-d)

2、2=2k）2021-10-2310本题算法(略)：l哪位同学做个陈述？2021-10-2311problem 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 th

3、e nth element in this sequence 2021-10-23122021-10-2313l1 -?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)l1 -2 -3 - 4 -5= min(3*2,2*3,1*5,1*7)2021-10-2314lf(n)=min(f(i)*2,f(j)*3,f(k)*5,f(m)*7)(ni,j,k,m)特别的：i,j,k,m 只有在本项被选中后才移动2021-10-2315v0v1v2v3v4v510010

4、30105502060起起点点终终点点最短最短路径路径路径路径长度长度v0v0v1v1无无v2v2（v0,v2v0,v2）1010v3v3(v0,v4,v3)(v0,v4,v3)5050v4v4(v0,v4)(v0,v4)30302021-10-2316求求源点到终点的最短路径源点到终点的最短路径的算法的算法的基本思想的基本思想: 按照最短路径的长度最短路径的长度递增的次序依次求得源点到其余各点的最短路径。2021-10-2317 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 路径长度最短的最短路径最短路径的特点：假设，从源点到顶点从源点到顶点v1的最短路径的最短路径是所有最短路径中长

5、度最短者。2021-10-2318下一条路径长度次短次短的最短路径最短路径的特点： 它只可能有两种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)。2021-10-2319再下一条路径长度次短的路径特点再下一条路径长度次短的路径特点: 它可能有三种情况：或者是直接从源点到该点(只含一条弧)； 或者是从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是从源点经过顶点v2，再到达该顶点。2021-10-2320其余最短路径的特点其余最短路径的特点：它或者是直接从源点到该点(只含一条弧)； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。2

6、021-10-2321 求最短路径的迪杰斯特拉算法：求最短路径的迪杰斯特拉算法：0 0）准备工作：）准备工作：设置辅助数组dist，其中每个分量distk 表示：当前所求得的从源点到其余各顶点 k 的最短路径。2021-10-23221）在所有从源点出发的弧中选取一条权）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。值最小的弧，即为第一条最短路径。infinitykvarcsgkdist0.v0和k之间存在弧v0和k之间不存在弧其中的最小值即为最短路径的长度其中的最小值即为最短路径的长度。2021-10-23232 2）修改其它各顶点的）修改其它各顶点的distdist k

7、k 值。值。( (为什么？为什么？) )具体操作：假设求得最短路径的顶点为u，若若 distu+g.arcsukdistk则将 distk 改为 distu+g.arcsuk。2021-10-23243 3）选出下一条最短路径，重复以上）选出下一条最短路径，重复以上操作，直到求出所有的最短路径。操作，直到求出所有的最短路径。搞定！搞定！说明说明: :求求两点之间两点之间的最短路径和的最短路径和求求一个点到其余所有点一个点到其余所有点的最短路的最短路径工作量一样。径工作量一样。2021-10-2325终点终点从从 v0v0到各终点的到各终点的d d值值i=1i=1i=2i=2i=3i=3i=4i

8、=4i=5i=5v1v1v2v21010v3v3v4v43030v5v5100100vjvjv2v2v0v1v2v3v4v510010301055020602021-10-2326v0v1v2v3v4v5终点终点从从 v0v0到各终点的到各终点的d d值值i=1i=1i=2i=2i=3i=3i=4i=4i=5i=5v1v1v2v21010v3v360605050v4v430303030v5v510010010010090906060vjvjv2v2v4v4v3v3v5v52021-10-2327v0v1v2v3v4v51001030105502060起起点点终终点点最短最短路径路径路径路径长度

9、长度v0v0v1v1无无v2v2（v0,v2v0,v2）1010v3v3(v0,v4,v3)(v0,v4,v3)5050v4v4(v0,v4)(v0,v4)30302021-10-23281074_doing homework2021-10-2329思考：如何自顶向下的分析？2021-10-2330思考：如何自底向上的计算？2021-10-2331图示说明（假设有3门功课）：1231,22,31,31,2,32021-10-2332图示说明（假设有4门功课）：12341,22,31,31,42,43,41,2,31,2,41,3,42,3,41,2,3,42021-10-2333图示说明（假设有4门功课）：12341,22,31,31,42,43,41,2,31,2,41,3,42,3,41,2,3,42021-10-2334象不象数塔？2021-10-2335l1003、1074、1087、1159、1160、1176l1024、1025、1058、1069、1081l1157、