DP動態(tài)規(guī)劃PPT學習教案

1、會計學1DP動態(tài)規(guī)劃動態(tài)規(guī)劃第1頁/共74頁第2頁/共74頁第3頁/共74頁第4頁/共74頁者最大者最大.第5頁/共74頁第6頁/共74頁第7頁/共74頁記憶化的功效第8頁/共74頁第9頁/共74頁第10頁/共74頁第11頁/共74頁顯然,從上圖可以看出,當前狀態(tài)通過決策,回到了以前狀態(tài).可見決策其實就是狀態(tài)之間的橋梁。而以前狀態(tài)也就決定了當前狀態(tài)的情況。數字三角形的決策就是選擇相鄰的兩個以前狀態(tài)的最優(yōu)值。第12頁/共74頁第13頁/共74頁第14頁/共74頁第15頁/共74頁第16頁/共74頁2 3 3 2 4 1 5 1 3 5 103 1 2 3 2 4 12 1 5 5 3 狀態(tài)的表示

2、狀態(tài)的表示fi,jfi,j表示前表示前i i個第一排的數字和前個第一排的數字和前j j個第二排的數字搭配的最優(yōu)值。個第二排的數字搭配的最優(yōu)值。當前的狀態(tài)就是當前你枚舉到的一組交錯的后面兩個位置當前的狀態(tài)就是當前你枚舉到的一組交錯的后面兩個位置. .例如上圖中當前狀態(tài)是例如上圖中當前狀態(tài)是3 3和和1(1(第一組交錯第一組交錯),),枚舉他的以前狀態(tài)就有枚舉他的以前狀態(tài)就有1 3.1 3.這樣在這樣在1 31 3之前會有一個最優(yōu)值存在之前會有一個最優(yōu)值存在, ,因此可以由此得到因此可以由此得到3 13 1的最優(yōu)值的最優(yōu)值. .第17頁/共74頁號為號為N N。第18頁/共74頁第19頁/共74頁

3、怎么怎么辦辦第20頁/共74頁當前所在的某個車站這一題的以前狀態(tài)其實只有這一題的以前狀態(tài)其實只有3種種.即滿足即滿足3種距離種距離(收費收費)情況的情況的3個車站個車站.要知道這要知道這3個車站可以先做一個預處理個車站可以先做一個預處理.顯然這顯然這3個車站在滿足距離限制的條件下應該越遠越好個車站在滿足距離限制的條件下應該越遠越好.第21頁/共74頁第22頁/共74頁第23頁/共74頁第24頁/共74頁第25頁/共74頁第26頁/共74頁第27頁/共74頁第28頁/共74頁或許你不明白我在說什么,那么我們通過題目來說明吧第29頁/共74頁第30頁/共74頁后后,乘積最大的一題也是乘積最大的一題

4、也是完全一樣的形式完全一樣的形式,誰還會誰還會去用搜索去用搜索?第31頁/共74頁第32頁/共74頁第33頁/共74頁尋找定量!第34頁/共74頁第35頁/共74頁第36頁/共74頁第37頁/共74頁第38頁/共74頁第39頁/共74頁第40頁/共74頁定量很不錯啊!第41頁/共74頁第42頁/共74頁第43頁/共74頁第44頁/共74頁第45頁/共74頁第46頁/共74頁對于所給出的矩陣找出一條最長的遞減鏈,滿足鏈中相鄰的兩個元素間都是在矩陣中相鄰的.上圖中所給出的矩陣中的最長鏈是1 2 3 425.第47頁/共74頁第48頁/共74頁第49頁/共74頁第50頁/共74頁第51頁/共74頁第

5、52頁/共74頁|講完了比較實用的兩種種動規(guī)的武器之后,我們來看看一些大家可能不太會做的動規(guī)類型第53頁/共74頁第54頁/共74頁第55頁/共74頁第56頁/共74頁第第i個房間個房間.用用fi,j來表來表示示.第57頁/共74頁K表示的是和I連接的一個房間,ci表示進入I號房間的花費.第58頁/共74頁會的總活躍指數最大。會的總活躍指數最大。第59頁/共74頁第60頁/共74頁j,0),j為為i的的i兒子）。兒子）。n這就是樹狀動規(guī)的基這就是樹狀動規(guī)的基本形態(tài)。本形態(tài)。第61頁/共74頁第62頁/共74頁第63頁/共74頁最小的結點有哪些。最小的結點有哪些。如有多個最小的如有多個最小的Ai，則都要輸出。這里則都要輸出。這里N=10000N=10000第64頁/共74頁