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

1、ACM程序設計杭州電子科技大學 劉春英9/22/20221今天，你報名 了嗎？月賽 9/22/20222每周一星（7）：08052233 9/22/20223第八講動態(tài)規(guī)劃（2）（Dynamic Programming）9/22/20224第一感覺：根據(jù)題目的要求，每次提的兩個物品重量差越小越好，是不是每次提的物品一定是重量相鄰的物品呢？證明：假設四個從小到大的數(shù)：a、b、c、d，只需證明以下表達式成立即可：(a-b)2+(c-d)2 (a-c)2+(b-d)2(a-b)2+(c-d)2=2k）n個物品選二對，9/22/20229本題算法(略)：哪位同學做個陳述？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思考：動態(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)轉移方程？F(n)=min(F(i)*2,F(j)*3,F(k)*5,F(m)*7)(ni,j,k,m)特別的：i,j,k,m 只有在本項被選中后才移動9/22/202214求最短路徑的基本思想: 按照

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

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

6、個點到其余所有點的最短路徑工作量一樣。9/22/202224練習：模擬求最短路徑終點從 V0到各終點的D值i=1i=2i=3i=4i=5V1V210V36050V43030V51001009060VjV2V4V3V5V0V1V2V3V4V510010301055020609/22/202226回顧原圖：最短路徑問題V0V1V2V3V4V51001030105502060起點終點最短路徑路徑長度V0V1無V2（V0,V2）10V3(V0,V4,V3)50V4(V0,V4)30V5(V0,V4,V3,V5)609/22/202227思考：如何自頂向下的分析？9/22/202229思考：如何自底向上的計算？9/22/202230圖示說明（假設有3門功課）：1231,22,31,31,2,39/22/202231圖示說明（假設有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練習題(HDOJ)：200909A