實驗五動態(tài)規(guī)劃問題算法設計.doc

《實驗五動態(tài)規(guī)劃問題算法設計.doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、寧夏師范學院數(shù)學與計算機科學學院《算法分析與設計》實驗報告實驗序號：5　　實驗項目名稱：動態(tài)規(guī)劃問題算法設計學　　號姓　　名專業(yè)、班實驗地點指導教師惠云時間一、實驗目的及要求（1）掌握使用動態(tài)規(guī)劃方法設計最優(yōu)值問題的方法；（2）能夠使用動態(tài)規(guī)劃算法設計策略設計矩陣連乘和最長公共子序列問題的算法；（3）掌握0-1背包問題的算法設計方法。二、實驗設備（環(huán)境）及要求1、環(huán)境要求：硬件：PC（PII以上，128M以上內(nèi)存）、因特網(wǎng)接入；軟件：WindowsXP操作系統(tǒng)、VC++6.0編程環(huán)境。2、實驗要求：(1)獨立完成實驗，源代碼書寫規(guī)范；(2)程序運行結果以屏幕截圖的方式粘貼在對應

2、位置，截圖必須清晰準確；(3)實驗完成后必須有實驗結果的分析及本次實驗的總結。三、實驗內(nèi)容與步驟1、設計求解n個矩陣連乘的最優(yōu)計算次序問題的程序，并將在最優(yōu)計算次序下所需的乘法次數(shù)及最優(yōu)計算次序在屏幕上顯示。n個矩陣的維數(shù)從鍵盤輸入。2、設計求解x和y兩個序列的最長公共子序列問題的程序，并將最長公共子序列的長度及最長公共子序列在屏幕上顯示。x和y序列從鍵盤輸入。3、設計求解0-1背包問題的程序，并將裝入背包的物品的最大價值及最優(yōu)裝入序列在屏幕上顯示。背包的最大容量，物品的重量、價值從鍵盤輸入。四、實驗結果與數(shù)據(jù)處理五、分析與討論1、比較備忘錄方法和動態(tài)規(guī)劃方法求矩陣連乘問題的特

3、點。2.分析求最長公共子序列長度和構造最長公共子序列兩種算法的時間復雜度。六、教師評語簽名：日期：年月日成績