動態(tài)規(guī)劃作業(yè).doc

1、動態(tài)規(guī)劃作業(yè)作業(yè) 1 1 動態(tài)規(guī)劃練習 ：為保證某一設(shè)備的正常運轉(zhuǎn)，需備有三種不同的零件 E 1 , E 2, E 3。若增加備用零件的數(shù)量，可提高設(shè)備正常運轉(zhuǎn)的可靠性，但增加了費用，而投資額僅為8000 元。已知備用零件數(shù)與它的可靠性和費用的關(guān)系如表1 所示?，F(xiàn)要求在既不超出投資額的限制，又能盡量提高設(shè)備運轉(zhuǎn)的可靠性的條件下，問各種零件的備件數(shù)量應(yīng)是多少為好？要寫出計算程序。解：設(shè)投資順序為 E1，E2，E3，階段編號逆向編號，即第一階段計算給E3 投資的效果。設(shè)ks 為第 k 階段的剩余款，k_ 為第 k 階段的撥款額，狀態(tài)轉(zhuǎn)移方程為k k k_ s s - =-1，目標函數(shù)為 ) 1 (

2、 ) 1 ( ) 1 ( ma_3 2 1P P P f + ´ + ´ + = ,其中1P ，2P ，3P 分別為 E1，E2，E3 增加的可靠性 第一階段：對 E3 的投資效果 決策表：s1_1 0 2 3 4 _1_f1 0 10 1 1 10 1 2 1 1.12 1.1 3 1 1.1 1.23 1.2 4 1 1.1 1.2 1.7 4 1.7 5 1 1.1 1.2 1.7 4 1.7 6 1 1.1 1.2 1.7 4 1.7 7 1 1.1 1.2 1.7 4 1.7 8 1 1.1 1.2 1.7 4 1.7第二階段，對 E2 的投資效果 由于 E1 最

3、多只需 3000，故 52>= s 千 決策表：s2_2 0 3 5 6 _2_f2 5 1.7 1.32 1.55 1.5 6 1.7 1.44 1.5 1.9 6 1.9 7 1.7 2.04 1.65 1.9 3 2.04 8 1.7 2.04 1.8 2.09 6 2.09 第三階段：對 E1 的投資效果 決策表: s3_3 0 2 3 4 _3_R3 8 2.09 2.09 1.8 0.7 0,2 2.09 回溯：有兩組最優(yōu)解 (1)_3=0,_2=3,_1=2,ma_f=2.09 (2)_3=1,_2=3,_1=0,ma_f=2.092 2 層次分析p 法練習 ：你已經(jīng)去過幾

4、家主要的摩托車商店，基本確定將從三種車型中選購一種，你選擇的標準主要有：價格、耗油量大小、舒適程度和外觀美觀情況。經(jīng)反復思考比較，構(gòu)造了它們之間的成對比較判斷矩陣。三種車型（記為 a , b , c ）關(guān)于價格、耗油量、舒適程度和外表美觀情況的成對比較判斷矩陣為：（1）根據(jù)上述矩陣可以看出四項標準在你心目中的比重是不同的，請按由重到輕順序?qū)⑺鼈兣懦?。?）哪輛車最便宜、哪輛車最省油、哪輛車最舒適、哪輛車最漂亮？ （3）用層次分析p 法確定你對這三種車型的喜歡程度（用百分比表示）。解：(1)由重到輕依次是價格、耗油量、舒適程度和外表美觀情況 (2)C 車最便宜，A 車最省油，A 車最舒適，B 車

5、最漂亮 (3) a、建立層次模型：目標層：選擇哪種車 準則層：價格耗油情況舒適度外表美觀度 方案層：A 車型B 車型C 車型 b、成對比較陣題目當中已給出 c、計算權(quán)向量并做一致性檢驗 運行結(jié)果得到權(quán)向量為 w=(0.5820,0.2786,0.0899,0.0495),CR=0.0734作者厲害到我不知道該用什么言語稱贊了。喜歡這里文字的風格。吉林師范大學計算機學院教案課 程 名 稱 院系級C 程序設(shè)計(算法部分)計算機學院計算機科學與技術(shù)09級教研室(系、實驗室) 計算機基礎(chǔ)教研室5 授 課 班 級 09計算機科學與技術(shù)3班 實習生鄭言系指導教師滕國文吉林師范大學計算機學院二一二年四月二十

6、五日（星期三5，6節(jié)）課型章節(jié)：動態(tài)規(guī)劃基本思想基要本參教考材資和料主：算法設(shè)計與分析p 教學目的：本課程以C語言為教授程序設(shè)計的描述語言，結(jié)合語言介紹程序設(shè)計的基本原理、技巧和方法。主要講授內(nèi)容包括程序設(shè)計動態(tài)規(guī)劃基本概念，動態(tài)規(guī)劃的基本步驟，動態(tài)規(guī)劃問題的特征。通過本課程的學習，為算法更好的學習，以及能用計算機解決一些實際問題打下堅實的基礎(chǔ)。 教學基本要求：掌握C語言中動態(tài)規(guī)劃的基本概念，動態(tài)規(guī)劃的基本步驟，動態(tài)規(guī)劃問題的特征。并能熟練使用C語言動態(tài)規(guī)劃思想解決一些簡單程序問題；掌握一些基本算法結(jié)構(gòu)及相關(guān)方法；熟悉程序設(shè)計的思想和編程技巧。 重點：動態(tài)規(guī)劃基本概念，動態(tài)規(guī)劃的基本步驟，動態(tài)

7、規(guī)劃問題的特征。 難點: 動態(tài)規(guī)劃的基本步驟 課型：理論課 教法：1.多媒體講解 2.舉例講解 教學內(nèi)容及過程： 1.課前回顧：枚舉法: 在進行歸納推理時，如果逐個考察了某類事件的所有可能情況，因而得出一般結(jié)論，那么這結(jié)論是可靠的，這種歸納方法叫做枚舉法2.數(shù)塔問題 有形如下圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的值最大。 簡單的進行選舉方法的引導，讓同學們主動思考到動態(tài)規(guī)劃的思想上了。 考慮一下：從頂點出發(fā)時到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。同

8、樣，下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時就非常明了。如數(shù)字2，只要選擇它下面較大值的結(jié)點19前進就可以了。所以實際求解時，可從底層開始，層層遞進，最后得到最大值。結(jié)論：自頂向下的分析p ，自底向上的計算。 #include #include int ma_(int _,int y) if(_>y)return _; elsereturn y; main int a100100; int i,j,n; scanf("d",&n); for(i=0;ifor(j=0;jscanf("d&quo

9、t;,&aij); for(i=n-2;i>=0;i-)for(j=0;jaij+=ma_(ai+1j,ai+1j+1); printf("dn",a00); 3.總結(jié)“動態(tài)規(guī)劃的基本思想”如果各個子問題不是獨立的，不同的子問題的個數(shù)只是多項式量級，如果我們能夠保存已經(jīng)解決的子問題的答案，而在需要的時候再找出已求得的答案，這樣就可以避免大量的重復計算。由此而來的基本思路是，用一個表記錄所有已解決的子問題的答案，不管該問題以后是否被用到，只要它被計算過，就將其結(jié)果填入表中。 4.總結(jié)“動態(tài)規(guī)劃的基本步驟”動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題

10、中，可能會有許多可行解。每一個解都對應(yīng)于一個值，我們希望找到具有最優(yōu)值（最大值或最小值）的那個解。設(shè)計一個動態(tài)規(guī)劃算法，通?？梢园匆韵聨讉€步驟進行：（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)解。5.總結(jié)“動態(tài)規(guī)劃問題的特征”動態(tài)規(guī)劃算法

11、的有效性依賴于問題本身所具有的兩個重要性質(zhì)：1、最優(yōu)子結(jié)構(gòu)：當問題的最優(yōu)解包含了其子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2、重疊子問題：在用遞歸算法自頂向下解問題時，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)，對每一個子問題只解一次，而后將其解保存在一個表格中，在以后盡可能多地利用這些子問題的解。 6.思考：免費餡餅 題目描述: 都說天上不會掉餡餅，但有一天gameboy正走在回家的小徑上，忽然天上掉下大把大把的餡餅。說來gameboy的人品實在是太好了，這餡餅別處都不掉，就掉落在他身旁的10米范圍內(nèi)。餡餅如果掉在了地上當然就不

12、能吃了，所以gameboy馬上卸下身上的背包去接。但由于小徑兩側(cè)都不能站人，所以他只能在小徑上接。由于gameboy平時老呆在房間里玩游戲，雖然在游戲中是個身手敏捷的高手，但在現(xiàn)實中運動神經(jīng)特別遲鈍，每秒種只有在移動不超過一米的范圍內(nèi)接住墜落的餡餅?，F(xiàn)在給這條小徑如圖標上坐標： 為了使問題簡化，假設(shè)在接下來的一段時間里，餡餅都掉落在0-10這11個位置。開始時gameboy站在5這個位置，因此在第一秒，他只能接到4,5,6這三個位置中期中一個位置上的餡餅。問gameboy最多可能接到多少個餡餅？（假設(shè)他的背包可以容納無窮多個餡餅）#include using namespace std; int a10000111; int ma_(int _,int y,int z) if(_>y) if(_>z) return _; else return z; else if(y>z) return y; else return z; int main int i,j,f,n,_,y; while(cin>>n) if