第六章-動態(tài)規(guī)劃法--實驗及練習PPT課件

1、我們畢業(yè)啦我們畢業(yè)啦 其實是答辯的標題地方其實是答辯的標題地方 算法設計與分析算法設計與分析 第第 六六 章章 動態(tài)規(guī)劃法動態(tài)規(guī)劃法 實驗實驗 1. 實驗題目實驗題目 編程實現(xiàn)圖示多段圖的最短路徑問題的動態(tài)規(guī)劃算法 2實驗目的實驗目的 （1）理解動態(tài)規(guī)劃算法的概念； （2）掌握動態(tài)規(guī)劃算法的基本要素； （3）掌握設計動態(tài)規(guī)劃算法的步驟； （4）通過應用范例學習動態(tài)規(guī)劃算法的設計技巧與策略。 1. 實驗題目實驗題目 給定由n個整數(shù)組成的序列(a1, a2, , an)，求該序列 形如 的子段和的最大值，當所有整數(shù)均為負整數(shù)時， 其最大子段和為0。 2. 實驗目的實驗目的 （1）深刻掌握動態(tài)規(guī)劃法

2、的設計思想并能熟練運用； j ik k a 3. 實驗要求實驗要求 （1）用動態(tài)規(guī)劃法設計最大子段和問題的算法； （2）比較用蠻力法、分治法和動態(tài)規(guī)劃法解決此問題的時 間性能； （3）給出測試數(shù)據(jù)，寫出程序文檔。 1. 實驗題目實驗題目 給定由n個整數(shù)組成的序列(a1, a2, , an)，求該序列 形如 的子段和的最大值，當所有整數(shù)均為負整數(shù)時， 其最大子段和為0。 2. 實驗目的實驗目的 （1）深刻掌握動態(tài)規(guī)劃法的設計思想并能熟練運用； j ik k a 3. 實驗要求實驗要求 （1）用動態(tài)規(guī)劃法設計最大子段和問題的算法； （2）比較用蠻力法、分治法和動態(tài)規(guī)劃法解決此問題的時 間性能； （

3、3）給出測試數(shù)據(jù)，寫出程序文檔。 【 問 題 描 述問 題 描 述 】 編 輯 距 離 L e v e n s h t e i n 距 離 ， 由 俄 羅 斯 科 學 家 Vladimir Levenshtein 在1965年提出。是指兩個字串之間，由一個轉成 另一個所需的最少編輯操作次數(shù)。給定兩個字符串S和T，對于T我們允許 三種操作： (1) 在任意位置添加任意字符 (2) 刪除存在的任意字符 (3) 修改任意字符 問最少操作多少次可以把字符串T變成S？ 【輸入輸入】 文件 input.txt 提供輸入數(shù)據(jù)，第一行為字符串A，第二行為字符串B。 【輸出輸出】 文件 output.txt 為

4、結果輸出文件，第一行為編輯距離d（A，B） PC/UVa IDs: 111101/10131, Popularity: B, Success rate: high Level: 2 【問題描述】 一些人認為，大象的體型越大，腦子越聰明。為了反駁這 一錯誤觀點，你想要分析一組大象的數(shù)據(jù)，找出盡量多的 大象組成一個體重嚴格遞增但 IQ 嚴格遞減的序列。 p 【輸入】 ：輸入包含若干大象的數(shù)據(jù)，每行一頭大象，直 到輸入結束。每頭大象的數(shù)據(jù)包括兩個整數(shù)：第一個是以 千克為單位的體重，第二個是以整百為單位的 IQ 指數(shù)。 兩個整數(shù)均在 1 到 10000之間。輸入最多包含 1000 頭大 象。兩頭大象可

5、能有相同的體重，或者相同的 IQ，甚至 體重和 IQ 都相同。 p 【輸出】 ：輸出第一行應當包括一個整數(shù) n，為找到的大 象序列的長度。接下來的 n 行，每行包含一個正整數(shù)，表 示大象。用 Wi 和 Si 表示輸入數(shù)據(jù)中第 i 行的兩個數(shù) ，則若找到的這一序列為 a1，a2， . ，an，則必須 有： W a1 W a2 . Sa2 . Sani Sample Input 6008 1300 6000 2100 500 2000 1000 4000 1100 3000 6000 2000 8000 1400 6000 1200 2000 1900 Sample Output 4 4 5 9

6、7 p 首先將所有大象按體重Wi升序排列，這樣該問題就轉化 為了最長上升遞減子序列LIS（Longest Increasing Subsequence）問題。 p 定義狀態(tài)d(i)，代表前i個大象中以大象i作為序列結尾的最 長上升子序列的長度。 p 狀態(tài)轉移方程：d(i) = max d(k)+1 | 1=ki, WkSi 回文串是指aba、abba、cccbccc、aaaa這種左右對稱的字符串。每 個字符串都可以通過向中間添加一些字符，使之變?yōu)榛匚淖址?。例如?abbc 添加2個字符可以變?yōu)?acbbca，也可以添加3個為 abbcbba。方案1 只需要添加2個字符，是所有方案中添加字符數(shù)

7、量最少的。 Input 輸入一個字符串Str，Str的長度 = 1000。 Output 輸出最少添加多少個字符可以使之變?yōu)榛匚淖执?Input示例示例 Abbc Output示例示例 2 p 題目描述 王強今天很開心，公司發(fā)給N元的年終獎。王強決定把年 終獎用于購物，他把想買的物品分為兩類：主件與附件， 附件是從屬于某個主件的，下表就是一些主件與附件的例 子： p 如果要買歸類為附件的物品，必須先買該附件所屬的主件。 p 每個主件可以有 0 個、 1 個或 2 個附件。附件不再有從屬于自己的 附件。 p 王強想買的東西很多，為了不超出預算，他把每件物品規(guī)定了一個重 要度，分為 5 等：用整

8、數(shù) 1 5 表示，第 5 等最重要。他還從因特 網(wǎng)上查到了每件物品的價格（都是 10 元的整數(shù)倍）。他希望在不超 過 N 元（可以等于 N 元）的前提下，使每件物品的價格與重要度的 乘積的總和最大。 p 設第 j 件物品的價格為 vj ，重要度為 wj ，共選中了 k 件物品， 編號依次為 j 1 ， j 2 ， j k ，則所求的總和為： vj 1 *wj 1 +vj 2 *wj 2 + +vj k *wj k 。（其中 * 為乘 號）請你幫助王強設計一個滿足要求的購物單。 p 輸入描述: 輸入的第 1 行，為兩個正整數(shù)，用一個空格隔開：N m（其中 N （ 32000 ）表示總錢數(shù)， m （ 60 ）為希望購買物品的個數(shù)。） 從第 2 行到第 m+1 行，第 j 行給出了編號為 j-1 的物品的基本數(shù)據(jù) ，每行 有 3 個非負整數(shù) v p q（其中 v 表示該物品的價格（ v0 ，表示該物品 為附件， q 是所屬主件的編號） p 輸出描述: 輸出文件只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘 積的總和的最大值（ 200000 ）。 國內(nèi)Online Judge 浙江工業(yè)大學 http:/ 杭州電子科技大學 http:/ 哈爾濱工業(yè)大學 http:/ a=showPr