動(dòng)態(tài)規(guī)劃2課件

1、ACM程序設(shè)計(jì)杭州電子科技大學(xué) 劉春英9/22/20221今天，你報(bào)名 了嗎？月賽 9/22/20222每周一星（7）：08052233 9/22/20223第八講動(dòng)態(tài)規(guī)劃（2）（Dynamic Programming）9/22/20224第一感覺：根據(jù)題目的要求，每次提的兩個(gè)物品重量差越小越好，是不是每次提的物品一定是重量相鄰的物品呢？證明：假設(shè)四個(gè)從小到大的數(shù)：a、b、c、d，只需證明以下表達(dá)式成立即可：(a-b)2+(c-d)2 (a-c)2+(b-d)2(a-b)2+(c-d)2=2k）n個(gè)物品選二對(duì)，9/22/20229本題算法(略)：哪位同學(xué)做個(gè)陳述？9/22/202210例2:

2、HDOJ_1058 Humble NumbersProblem 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 s

3、equence 9/22/202211思考：動(dòng)態(tài)規(guī)劃的特征體現(xiàn)在什么地方？9/22/202212算法分析：典型的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)9/22/202213狀態(tài)轉(zhuǎn)移方程？F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7)(ni,j,k,m)特別的：i,j,k,m 只有在本項(xiàng)被選中后才移動(dòng)9/22/202214求最短路徑的基本思想: 按照

4、最短路徑的長度遞增的次序依次求得源點(diǎn)到其余各點(diǎn)的最短路徑。9/22/202216 在這條路徑上，必定只含一條弧，并且這條弧的權(quán)值最小。 路徑長度最短的最短路徑的特點(diǎn)：假設(shè)，從源點(diǎn)到頂點(diǎn)V1的最短路徑是所有最短路徑中長度最短者。9/22/202217路徑長度第三短的路徑特點(diǎn): 它可能有三種情況：或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)；或者是從源點(diǎn)經(jīng)過頂點(diǎn)v2，再到達(dá)該頂點(diǎn)。9/22/202219其余最短路徑的特點(diǎn)：它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)； 或者是從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。9/22/202220迪杰斯特拉算

5、法：0）準(zhǔn)備工作：設(shè)置輔助數(shù)組Dist，其中每個(gè)分量Distk 表示：當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn) k 的最短路徑。9/22/2022211）在所有從源點(diǎn)出發(fā)的弧中選取一條權(quán)值最小的弧，即為第一條最短路徑。V0和k之間存在弧V0和k之間不存在弧其中的最小值即為最短路徑的長度。9/22/2022222）修改其它各頂點(diǎn)的Distk值。(為什么？)具體操作：假設(shè)求得最短路徑的頂點(diǎn)為u，若 Distu+G.arcsukDistk則將 Distk 改為 Distu+G.arcsuk。9/22/2022233）選出下一條最短路徑，重復(fù)以上操作，直到求出所有的最短路徑搞定！說明:求兩點(diǎn)之間的最短路徑和求一

6、個(gè)點(diǎn)到其余所有點(diǎn)的最短路徑工作量一樣。9/22/202224練習(xí)：模擬求最短路徑終點(diǎn)從 V0到各終點(diǎn)的D值i=1i=2i=3i=4i=5V1V210V36050V43030V51001009060VjV2V4V3V5V0V1V2V3V4V510010301055020609/22/202226回顧原圖：最短路徑問題V0V1V2V3V4V51001030105502060起點(diǎn)終點(diǎn)最短路徑路徑長度V0V1無V2（V0,V2）10V3(V0,V4,V3)50V4(V0,V4)30V5(V0,V4,V3,V5)609/22/202227思考：如何自頂向下的分析？9/22/202229思考：如何自底向上的計(jì)算？9/22/202230圖示說明（假設(shè)有3門功課）：1231,22,31,31,2,39/22/202231圖示說明（假設(shè)有4門功課）：12341,22,31,31,42,43,41,2,31,2,41,3,42,3,41,2,3,49/22/202232象不象數(shù)塔？9/22/202233附錄：DP練習(xí)題(HDOJ)：200909A