第六章-動(dòng)態(tài)規(guī)劃法--實(shí)驗(yàn)及練習(xí)PPT課件

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

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

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

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

5、能有相同的體重，或者相同的 IQ，甚至 體重和 IQ 都相同。 p 【輸出】 ：輸出第一行應(yīng)當(dāng)包括一個(gè)整數(shù) n，為找到的大 象序列的長(zhǎng)度。接下來(lái)的 n 行，每行包含一個(gè)正整數(shù)，表 示大象。用 Wi 和 Si 表示輸入數(shù)據(jù)中第 i 行的兩個(gè)數(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升序排列，這樣該問(wèn)題就轉(zhuǎn)化 為了最長(zhǎng)上升遞減子序列LIS（Longest Increasing Subsequence）問(wèn)題。 p 定義狀態(tài)d(i)，代表前i個(gè)大象中以大象i作為序列結(jié)尾的最 長(zhǎng)上升子序列的長(zhǎng)度。 p 狀態(tài)轉(zhuǎn)移方程：d(i) = max d(k)+1 | 1=ki, WkSi 回文串是指aba、abba、cccbccc、aaaa這種左右對(duì)稱的字符串。每 個(gè)字符串都可以通過(guò)向中間添加一些字符，使之變?yōu)榛匚淖址?。例如?abbc 添加2個(gè)字符可以變?yōu)?acbbca，也可以添加3個(gè)為 abbcbba。方案1 只需要添加2個(gè)字符，是所有方案中添加字符數(shù)

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

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