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

1、動(dòng)態(tài)規(guī)劃ppt第1頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一簡(jiǎn)介動(dòng)態(tài)規(guī)劃簡(jiǎn)稱DP，是在20世紀(jì)50年代由一位卓越的美國(guó)數(shù)學(xué)家Richcard Bellman發(fā)明的。它作為一種重要的工具在應(yīng)用數(shù)學(xué)中被廣泛的應(yīng)用。它不僅可以解決特定類型的優(yōu)化問(wèn)題，還可以作為一種通用的算法設(shè)計(jì)技術(shù)來(lái)使用。第2頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一DP的實(shí)質(zhì)利用問(wèn)題的所具有的重疊子問(wèn)題的性質(zhì)進(jìn)行記憶化求解。（用空間換時(shí)間）第3頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一求Fibonacci數(shù)：f(n) = f(n-1) + f(n-2) n2 f(1)=f(2)=1

2、第4頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一常規(guī)遞歸int Non_DP(int n) if (n=1 | n=2) return 1; else return Non_DP(n-1) + Non_DP(n-2); 指數(shù)級(jí)時(shí)間復(fù)雜度，無(wú)法忍受第5頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一兩種實(shí)現(xiàn)方式自底向上(bottom up)int DP_Bottom_Up(int n) memo1 = memo2 = 1; for (int i=3; i=n; i+)memoi = memoi-1 + memoi-2;return memon;第6頁(yè)，共50頁(yè)，2022年

3、，5月20日，15點(diǎn)16分，星期一自頂向下（top down） （這樣寫法也叫記憶搜索）int DP_Top_Down(int n) if (n = 1 | n = 2) return 1;if (memon != 0) return memon;memon = DP_Top_Down(n-1) + DP_Top_Down(n-2);return memon;第7頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一基本概念最短路問(wèn)題AB1B2C1C2C3C4D1D2D3E求A到E的最短路徑。第8頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一直觀的方法是用回溯法搜索。時(shí)間復(fù)雜度

4、為指數(shù)級(jí)。低效的原因：沒有充分利用重疊子問(wèn)題的性質(zhì)。第9頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一此圖有明顯的次序，可以劃分為5階段。AB1B2C1C2C3C4D1D2D3E階段0階段1階段2階段3階段4第10頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一設(shè) Diskx 為第k階段城市x到城市E的最短路徑長(zhǎng)度。map i j 為i，j兩個(gè)城市間的距離。遞歸方程為Diskx = min Disk+1y+mapx,y 此問(wèn)題時(shí)間復(fù)雜度降為O(n2).第11頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一狀態(tài)：貼切，簡(jiǎn)潔的描述出事物性質(zhì)的單元量。例如：Disx。

5、要求：狀態(tài)與狀態(tài)之間可以轉(zhuǎn)移，以便有初始狀態(tài)逐漸轉(zhuǎn)移到目標(biāo)狀態(tài)，找到問(wèn)題的解。階段：若干性質(zhì)相近可以同時(shí)處理的狀態(tài)的集合。就是計(jì)算狀態(tài)的順序。要求：每個(gè)階段中狀態(tài)的取值只與這個(gè)階段之前的階段中的狀態(tài)有關(guān)，與這個(gè)階段之后的階段中的狀態(tài)無(wú)關(guān)。第12頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一狀態(tài)轉(zhuǎn)移方程：前一個(gè)階段中的狀態(tài)轉(zhuǎn)移到后一個(gè)階段的狀態(tài)得演變規(guī)律，即相鄰兩個(gè)階段的狀態(tài)變化方程。fk(i) = opt fk-1(j) + cost(i,j) k階段的i狀態(tài)與k-1階段的j狀態(tài)有關(guān)決策：計(jì)算每個(gè)狀態(tài)時(shí)作出的選擇。第13頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一無(wú)后

6、效性：決策之取決于當(dāng)前狀態(tài)的特征因素，而和到達(dá)此狀態(tài)的方式無(wú)關(guān)。也就是每個(gè)階段中狀態(tài)的取值只與這個(gè)階段之前的階段中的狀態(tài)有關(guān)，與這個(gè)階段之后的階段中的狀態(tài)無(wú)關(guān)。如果當(dāng)前定義的狀態(tài)不滿足無(wú)后效性，應(yīng)重新定義。第14頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一一維狀態(tài)存儲(chǔ)問(wèn)題硬幣問(wèn)題1：有n種硬幣，每種硬幣的面值為vi元，且只有一枚，問(wèn)用這n種硬幣找零S元的方法數(shù)。設(shè)dij為前i種硬幣組成j元的方法數(shù)。dij = di-1j + di-1j-vid00=1,d01S=0空間復(fù)雜度為O(n2),浪費(fèi)！第15頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一d0=1; d1S=0

7、;for (i=1; i=vi; j-) dj += dj-vi; 第16頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一0-1背包問(wèn)題：給定n種物品和一背包。物品i的重量是wi，其價(jià)值為vi，背包的容量為c。問(wèn)應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大?第17頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一設(shè)m(i,j)是背包容量為j，可選擇物品為i，i+1，,n時(shí)，0-1背包問(wèn)題的最優(yōu)值。m(i,j) = max m(i+1,j), m(i+1,j-wi)+vi j=wim(i+1,j)0=j=wn 0 0=jwn第18頁(yè)，共50頁(yè)，2022年，5月20

8、日，15點(diǎn)16分，星期一d0c=0;for (i=1; i=wi; j-) dj = max(dj,dj-wi+vi); 第19頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一推薦題目：/problem?id=1384 Piggy-Bank 第20頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一硬幣問(wèn)題2：有n種硬幣，每種硬幣的面值為vi元，有mi枚，問(wèn)用這n種硬幣找零S元的方法數(shù)。第21頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一d0=1;d1S=0;for (i=1; i=vi; j-)for(k=1;k=0) dj += dj-k*vi; 第22頁(yè)，共5

9、0頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一硬幣問(wèn)題3：有n種硬幣，每種硬幣的面值為vi元，有無(wú)數(shù)枚，問(wèn)用這n種硬幣找零S元的方法數(shù)。第23頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一d0=1;d1S=0;for (i=1; i=vi; j-)for(k=1;k+) if (j-k*vi=0) dj += dj-k*vi;else break; 第24頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一d0=1; d1S=0;for (i=1; i=n; i+) for (j=vi;j=S; j+) /無(wú)數(shù)的時(shí)候是順向 dj += dj-vi; 第25頁(yè)，共50頁(yè)，2

10、022年，5月20日，15點(diǎn)16分，星期一推薦題目： 寒冰王座 Big Event in HDU第26頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一/problem?id=2614 Old Wine Into New Bottles有n種小瓶子，每種瓶子容量范圍是Vi1Vi2，要灌滿容量為L(zhǎng)的大瓶子。問(wèn)最少差多少體積沒有灌滿。設(shè)di表示體積為i是否可以達(dá)到。若v可取到，則di=di | di-v第27頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一d0=1;d1L=0;for(i=0;in;i+) for(j=0;j=L-vi1;j+) if (dj=1) for(k=v

11、i1;k=vi2;k+) dj+k=1; 第28頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一最大子段和問(wèn)題：給定由n個(gè)整數(shù)(可能為負(fù)整數(shù))組成的序列a1,a2,an，求該序列形如的 子段和的最大值。第29頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一設(shè)bi為到ai截至且包括ai的字段最大和。int maxsum()int sum=0,b=0;for(int i=0;i0) b+=ai; /正的就連接起來(lái)else b=ai;/不然重新來(lái)過(guò)if (bsum) sum=b;/sum記錄的一直是最大的值return sum;第30頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)1

12、6分，星期一 最大連續(xù)子序列引申問(wèn)題：最大子矩陣和問(wèn)題最大m段子段和問(wèn)題 第31頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一最長(zhǎng)遞增子序列（LIS）常規(guī)DP，時(shí)間復(fù)雜度為O(n2)。存在一種特殊的方法，時(shí)間復(fù)雜度為O（n*logk)。第32頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一問(wèn)題描述：給定N（N = 1000000）個(gè)數(shù)，請(qǐng)?jiān)谄渲姓页鲎铋L(zhǎng)的一個(gè)上升鏈（嚴(yán)格上升）。例：11029384756其中最長(zhǎng)上升序列長(zhǎng)度為6，是：1 2 3 4 5 6。第33頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一算法1：我們令fi表示前i個(gè)數(shù)中找到的以第i個(gè)數(shù)num

13、i結(jié)尾的最長(zhǎng)鏈的長(zhǎng)度。那么，很容易列出方程f0 = 0;fi = max(fj | j I and numj numi) + 11 = I = N最后結(jié)果是：ans = max(fi | 1 = I = N)第34頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一上述算法的復(fù)雜度是O(N2)，類似第一題，引入si表示fi是由哪個(gè)狀態(tài)轉(zhuǎn)移過(guò)來(lái)的，則可逆推出最長(zhǎng)升鏈。現(xiàn)在我們?cè)倏匆幌逻@個(gè)問(wèn)題的一個(gè)變形：請(qǐng)你用最少的不上升序列覆蓋這N個(gè)數(shù)。第35頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一上面的例子最少要用6條非升鏈覆蓋：1 2 34510 9876再舉一個(gè)例子(N = 11)

14、：100 89 99 89 76 75 92 83 54 90 1第36頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一要用3條非升鏈：100 89 89 76 75 54 199 92 8390而我們?cè)儆^察一下它的最長(zhǎng)升鏈，其中一條是：75 83 90，長(zhǎng)度也為3！ 第37頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一這是巧合還是必然？這是必然！可以證明非升鏈覆蓋問(wèn)題和最長(zhǎng)升鏈問(wèn)題是同解的。同樣，升鏈覆蓋、降鏈覆蓋、非降鏈覆蓋和最長(zhǎng)非升鏈、最長(zhǎng)非降鏈、最長(zhǎng)降鏈同解?？谠E：前面加“非”字大家可以想象證明，等大家了解了算法2，就自然明白了。第38頁(yè)，共50頁(yè)，2022年，5

15、月20日，15點(diǎn)16分，星期一算法2：由于N的規(guī)模，算法一是在太慢了。這里介紹一種O(nlogn)的算法。首先定義數(shù)組D：Di（1 = I = N）表示目前為止，所有長(zhǎng)度為i的升鏈中，最后一個(gè)元素的最小可能值。如當(dāng)前找到兩個(gè)長(zhǎng)度為3的升鏈：2 3 4；1 3 9 那么D3 = 4。顯然，對(duì)于同樣長(zhǎng)度的升鏈，結(jié)尾越小越容易拓展成更長(zhǎng)的升鏈。并且可知D是一個(gè)嚴(yán)格升鏈（若其中Di+1 = numi and (p = 0 or Dp 1 s，說(shuō)明找到更長(zhǎng)的鏈，更新s。第40頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一例如：1 3 2 5 4 5initial s = 0 step1 s

16、= 1 D1 = 1step2 s = 2 D1 = 1 D2 = 3step3 s = 2 D1 = 1 D2 = 2step4 s = 3 D1 = 1 D2 = 2 D3 = 5step5 s = 3 D1 = 1 D2 = 2 D3 = 4step6 s = 4 D1 = 1 D2 = 2 D3 = 4 D4 = 5第41頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一顯然這個(gè)算法是O(nlogn)的。同樣這個(gè)算法證明了前面討論的變形的正確性。首先，本算法實(shí)際上構(gòu)造出了用最長(zhǎng)升鏈長(zhǎng)度（MAXL）條非升鏈覆蓋這N個(gè)數(shù)的一組解。我們只需要證明至少要用MAXL條非升鏈才能完成覆蓋即

17、可，顯然，最長(zhǎng)升鏈就需要MAXL條降鏈覆蓋。證畢。第42頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一推薦題目：/problem?id=1631 Bridging Signals /problem?id=2336 Ferry Loading II第43頁(yè)，共50頁(yè)，2022年，5月20日，15點(diǎn)16分，星期一二維狀態(tài)存儲(chǔ)問(wèn)題矩陣連乘問(wèn)題 （MCM）A(m*n) * B(n*q) cost=m*n*qA1 (10 x 100), A2 (100 x 5), A3 (5 x 50)(A1 (A2 A3) = 100 x 5 x 50 + 10 * 100 * 50 = 75000 (A1 A2) A3) = 10 x 100 x 5 + 10 x 5 x 50 = 7500 第44頁(yè)，共50頁(yè)，20