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

1、ACM程序設(shè)計7/28/20221今天，你 了嗎？AC7/28/20222每周一星（3）：Lomen 7/28/20223第四講動態(tài)規(guī)劃(1) （Dynamic programming）7/28/20224先熱身一下7/28/20225(1466)計算直線的交點數(shù)問題描述： 平面上有n條直線，且無三線共點，問這些直線能有多少種不同交點數(shù)。輸入：n（n=20）輸出：每個測試實例對應(yīng)一行輸出，從小到大列出所有相交方案，其中每個數(shù)為可能的交點數(shù)。樣例輸入4樣例輸出0 3 4 5 67/28/20226初步分析:我們知道:n條直線互不平行且無三線共點的最多交點數(shù)max=1+2+(n-1)=n(n-1)

2、/2,但本題不這么簡單，因為問題問的是：這些直線有多少種不同的交點數(shù)？7/28/20227思考2分鐘:如何解決?7/28/20228然后，假設(shè) 0+4*0+0=0；2、第四條與其中兩條平行，交點數(shù)為0+(n-1)*1+0=3;3、第四條與其中一條平行，這兩條平行直線和另外兩點直線的交點數(shù)為(n-2)*2=4,而另外兩條直線既可能平行也可能相交，因此可能交點數(shù)為： 0+（n-2）*2+0=4 或者 0+(n-2)*2+1=5 4、 第四條直線不與任何一條直線平行，交點數(shù)為： 0+(n-3)*3+0=3 或0+ (n-3)*3+2=5 或0+ (n-3)*3+3=6即n=4時，有0個，3個，4個，

3、5個，6個不同交點數(shù)。重點分析n的情況：7/28/202211從上述n=4的分析過程中，我們發(fā)現(xiàn)：m條直線的交點方案數(shù)=（m-r）條平行線與r條直線交叉的交點數(shù) + r條直線本身的交點方案=（m-r）*r+r條之間本身的交點方案數(shù)（0=r 109=10億）。試想一下：7/28/202215 拒絕暴力，倡導(dǎo)和諧7/28/202216從頂點出發(fā)時到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。同樣，下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時就非常明了。如數(shù)字2，只要選擇它

4、下面較大值的結(jié)點19前進(jìn)就可以了。所以實際求解時，可從底層開始，層層遞進(jìn)，最后得到最大值。結(jié)論：自頂向下的分析，自底向上的計算?？紤]一下：7/28/202217二、思考題：最長有序子序列I012345678NumI1472583697/28/202218解決方案：I012345678NumI147258369FI1232343457/28/202219三、1160 FatMouses Speed Sample Input6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900

5、 Sample Output4 4 5 9 77/28/202220題目分析：設(shè)Micei.W表示第i只老鼠的重量，Micei.S表示第i只老鼠的速度。我們先對Mice進(jìn)行排序，以W為第一關(guān)鍵字，從小到大，S為第二關(guān)鍵字，從大到小。設(shè)fi為Micei至Micen最長的序列長度?？紤]某一個fi，則有： fi = max(fi, fj+1) (1=j Micej.W，Micei.S Micej.S) 其中，初始條件為fi=1 (i=1, 2, ., n)。7/28/202221Qestion:兩個問題有本質(zhì)區(qū)別嗎？7/28/202222思考（期末考試題）：Super Jumping! Jumpin

6、g!Jumping! 7/28/202223解題思路？7/28/202224四、1159 Common SubsequenceSample Inputabcfbc abfcabprogramming contest abcd mnp Sample Output 4 2 07/28/202225輔助空間變化示意圖7/28/202226f(i,j)= 由于f(i,j)只和f(i-1,j-1), f(i-1,j)和f(i,j-1)有關(guān), 而在計算f(i,j)時, 只要選擇一個合適的順序, 就可以保證這三項都已經(jīng)計算出來了, 這樣就可以計算出f(i,j). 這樣一直推到f(len(a),len(b)就

7、得到所要求的解了.f(i-1,j-1)+1 (ai=bj)max(f(i-1,j),f(i,j-1) (ai!=bj) 子結(jié)構(gòu)特征：7/28/202227理論小結(jié)7/28/202228如果各個子問題不是獨立的，不同的子問題的個數(shù)只是多項式量級，如果我們能夠保存已經(jīng)解決的子問題的答案，而在需要的時候再找出已求得的答案，這樣就可以避免大量的重復(fù)計算。由此而來的基本思路是，用一個表記錄所有已解決的子問題的答案，不管該問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。 一、動態(tài)規(guī)劃的基本思想 7/28/202229二、動態(tài)規(guī)劃的基本步驟 動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題

8、中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值（最大值或最小值）的那個解。設(shè)計一個動態(tài)規(guī)劃算法，通?？梢园匆韵聨讉€步驟進(jìn)行： 7/28/202230（1）找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。（2）遞歸地定義最優(yōu)值。（3）以自底向上的方式計算出最優(yōu)值。（4）根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造一個最優(yōu)解。其中（1）（3）步是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省去。若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟（4）。此時，在步驟（3）中計算最優(yōu)值時，通常需記錄更多的信息，以便在步驟（4）中，根據(jù)所記錄的信息，快速構(gòu)造出一個最優(yōu)解?；静襟E 7/28/

9、202231三、動態(tài)規(guī)劃問題的特征 動態(tài)規(guī)劃算法的有效性依賴于問題本身所具有的兩個重要性質(zhì)：1、最優(yōu)子結(jié)構(gòu)：當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2、重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。7/28/202232思考：免費餡餅 7/28/202233如何解決？請發(fā)表見解 7/28/202234Any question?7/28/202235課后任務(wù)：一、DIY在線作業(yè)(4):2008ACM ProgrammingExe