動態(tài)規(guī)劃實例源代碼

1、習(xí)題1 最長公共子序列 一個給定序列的子序列是在該序列中刪去若干元素后得到的序列。 確切 地說，若給定序列X=vx1, x2, , xm，則另一序列Z=vz1, z2, , zk是X 的子序列是指存在一個嚴(yán)格遞增的下標(biāo)序列 ，使得對于 所有j=1,2, ,k有解答如下：a) 最長公共子序列的結(jié)構(gòu) 若用窮舉搜索法，耗時太長，算法需要指數(shù)時間。 易證最長公共子序列問題也有最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)序列X=和丫=的一個最長公共子序列 Z=，貝U:i. 若xm=yn，貝U zk=xm=yn且Zk-1是Xm-1和Yn-1的最長公共子序列；ii. 若xm工yn且zkz xm，貝U Z是Xm-1和丫的最長公共子序列；

2、iii. 若xm工yn且zkzyn，則Z是X和Yn-1的最長公共子序列。其中 Xm-1=， Yn-1=， Zk-1=。最長公共子序列問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。b) 子問題的遞歸結(jié)構(gòu) 由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出 X=和丫=的最長公共子序列，可按以下方式遞歸地進(jìn) 行:當(dāng) xm=yn 時，找出 Xm-1 和 Yn-1 的最長公共子序列，然后在其尾 部加上xm(=yn)即可得X和Y的一個最長公共子序列。當(dāng) xm工yn時， 必須解兩個子問題，即找出 Xm-1 和 Y 的一個最長公共子序列及 X 和 Yn-1 的一個最長公共子序列。這兩個公共子序列中較長者即為 X 和 Y 的一個最長公

3、共子序列。由此遞歸結(jié)構(gòu)容易看到最長公共子序列問題具有子問題重疊性質(zhì)。例 如，在計算 X 和 Y 的最長公共子序列時，可能要計算出 X 和 Yn-1 及 Xm-1 和 Y 的最長公共子序列。 而這兩個子問題都包含一個公共子問題， 即計算 Xm-1 和 Yn-1 的最長公共子序列。我們來建立子問題的最優(yōu)值的遞歸關(guān)系。 用 ci,j 記錄序列 Xi 和 Yj 的最 長公共子序列的長度。其中 Xi=， Yj=。當(dāng) i=0 或 j=0 時，空序列是 Xi 和 Yj 的最長公共子序列，故 ci,j=0 。建 立遞歸關(guān)系如下：c) 計算最優(yōu)值由于在所考慮的子問題空間中，總共只有 9 (m*n)個不同的子問題

4、，因 此，用動態(tài)規(guī)劃算法自底向上地計算最優(yōu)值能提高算法的效率。 計算最長公共子序列長度的動態(tài)規(guī)劃算法 LCS_LENGTH(X,Y) 以序列X=和Y=作為輸入。輸出兩個數(shù)組 cO.m ,0.n和b1.m ,1.n。其中ci,j存儲Xi與Yj的最長公共子序列的 長度， bi,j 記錄指示 ci,j 的值是由哪一個子問題的解達(dá)到的， 這在構(gòu)造 最長公共子序列時要用到。 最后， X 和 Y 的最長公共子序列的長度記錄 于 cm,n中。程序如下：#include#includeint lcs_length(char x, char y);int main()char x100,y100;int len

5、;while(1) scanf(%s%s,x,y);if(x0=0) / 約定第一個字符串以 0開始表示結(jié)束break;len=lcs_length(x,y);printf(%dn,len);int lcs_length(char x, char y )int m,n,i,j,l100100;m=strlen(x);n=strlen(y);for(i=0;im+1;i+)li0=0;for(j=0;jn+1;j+)l0j=0; for(i=1;i=m;i+) for(j=1;jli-1j)lij=lij-1;elselij=li-1j;return lmn;由于每個數(shù)組單元的計算耗費 o時間，

6、算法lcs_length耗時O(mn)思考：空間能節(jié)約嗎？2 計算矩陣連乘積 在科學(xué)計算中經(jīng)常要計算矩陣的乘積。 矩陣 A 和 B 可乘的條件是矩陣 A的列數(shù)等于矩陣B的行數(shù)。若A是一個px q的矩陣，B是一個qx r 的矩陣，則其乘積 C=AB是一個px r的矩陣。由該公式知計算 C=AB 總共需要 pqr 次的數(shù)乘。其標(biāo)準(zhǔn)計算公式為：現(xiàn)在的問題是，給定 n 個矩陣 A1,A2, , ,An 。其中 Ai 與 Ai+1 是可乘的，i=1,2, ,n-1。要求計算出這n個矩陣的連乘積A1A2, An。 遞歸公式：程序如下：#includeint main()int p101,i,j,k,r,t

7、,n;int m101101; / 為了跟講解時保持一致數(shù)組從 1 開始int s101101; / 記錄從第 i 到第 j 個矩陣連乘的斷開位置scanf(%d,&n);for(i=0;i=n;i+)seanf(%d,&pi); / 讀入 pi的值(注意：p0到 pn共 n+1 項)for(i=1;i=n;i+) / 初始化 mii=0mii=0;for(r=1;rn;r+) /r 為 i、j 相差的值for(i=1;in;i+) /i 為行j=i+r; /j 為列mij=mi+1j+pi-1*pi*pj; / 給 mij 賦初值sij=i;for(k=i+1;kj;k+)t=mik+mk+

8、1j+pi-1*pk*pj;if(tmij)mij=t; /mij 取最小值sij=k;printf(%d,m1n);3 凸多邊形的最優(yōu)三角剖分 多邊形是平面上一條分段線性的閉曲線。 也就是說，多邊形是由一系列 首尾相接的直線段組成的。組成多邊形的各直線段稱為該多邊形的邊。 多邊形相接兩條邊的連接點稱為多邊形的頂點。 若多邊形的邊之間除了 連接頂點外沒有別的公共點， 則稱該多邊形為簡單多邊形。 一個簡單多 邊形將平面分為 3 個部分： 被包圍在多邊形內(nèi)的所有點構(gòu)成了多邊形的 內(nèi)部；多邊形本身構(gòu)成多邊形的邊界； 而平面上其余的點構(gòu)成了多邊形 的外部。 當(dāng)一個簡單多邊形及其內(nèi)部構(gòu)成一個閉凸集時，稱

9、該簡單多邊 形為凸多邊形。 也就是說凸多邊形邊界上或內(nèi)部的任意兩點所連成的直 線段上所有的點均在該凸多邊形的內(nèi)部或邊界上。 通常，用多邊形頂點的逆時針序列來表示一個凸多邊形，即P=表示具有 n 條邊 vOv1 , v1v2, ,vn-1vn 的一個凸多邊形，其中，約定 v0=vn 。若 vi 與 vj 是多邊形上不相鄰的兩個頂點，則線段 vivj 稱為多邊形的一 條弦。弦將多邊形分割成凸的兩個子多邊形 和。多邊形的三角剖分是一個將多邊形分割成互不重迭的三角形的弦的集合T。如圖是一個凸多邊形的兩個不同的三角剖分。凸多邊形最優(yōu)三角剖分的問題是：給定一個凸多邊形P= 以及定義在由多邊形的邊和弦組成的

10、三角形上的 權(quán)函數(shù)3。要求確定該凸多邊形的一個三角剖分，使得該三角剖分對應(yīng) 的權(quán)即剖分中諸三角形上的權(quán)之和為最小?？梢远?義三 角 形 上各種 各樣的 權(quán) 函 數(shù) W 。 例如：定 義 3 （ vivjvk）=|vivj|+|vivk|+|vkvj| ，其中，|vivj| 是點 vi 至U vj 的歐氏距離。相應(yīng) 于此權(quán)函數(shù)的最優(yōu)三角剖分即為最小弦長三角剖分。（注意：解決此問題的算法必須適用于任意的權(quán)函數(shù) ）4 防衛(wèi)導(dǎo)彈 一種新型的防衛(wèi)導(dǎo)彈可截?fù)舳鄠€攻擊導(dǎo)彈。它可以向前飛行， 也可以用 很快的速度向下飛行，可以毫無損傷地截?fù)暨M(jìn)攻導(dǎo)彈， 但不可以向后或 向上飛行。但有一個缺點，盡管它發(fā)射時可以達(dá)

11、至任意高度，但它只能 截?fù)舯人洗谓負(fù)魧?dǎo)彈時所處高度低或者高度相同的導(dǎo)彈。 現(xiàn)對這種新 型防衛(wèi)導(dǎo)彈進(jìn)行測試，在每一次測試中，發(fā)射一系列的測試導(dǎo)彈（這些 導(dǎo)彈發(fā)射的間隔時間固定，飛行速度相同） ，該防衛(wèi)導(dǎo)彈所能獲得的信 息包括各進(jìn)攻導(dǎo)彈的高度，以及它們發(fā)射次序?，F(xiàn)要求編一程序，求在 每次測試中， 該防衛(wèi)導(dǎo)彈最多能截?fù)舻倪M(jìn)攻導(dǎo)彈數(shù)量， 一個導(dǎo)彈能被截 擊應(yīng)滿足下列兩個條件之一：a）它是該次測試中第一個被防衛(wèi)導(dǎo)彈截?fù)舻膶?dǎo)彈；b）它是在上一次被截?fù)魧?dǎo)彈的發(fā)射后發(fā)射，且高度不大于上一次被截?fù)?導(dǎo)彈的高度的導(dǎo)彈。輸入數(shù)據(jù)：第一行是一個整數(shù) n,以后的n各有一個整數(shù)表示導(dǎo)彈的高 度。輸出數(shù)據(jù)：截?fù)魧?dǎo)彈的最大

12、數(shù)目。分析：定義 li 為選擇截?fù)舻?i 個導(dǎo)彈，從這個導(dǎo)彈開始最多能截?fù)舻膶?dǎo) 彈數(shù)目。由于選擇了第 i 枚導(dǎo)彈，所以下一個要截?fù)舻膶?dǎo)彈 j 的高度要小于等于它的高度，所以li應(yīng)該等于從i + 1到n的每一個j,滿足hj=hi的 j 中 lj 的最大值。程序如下：#includeint main()int i,j,n,max,h100,l100; scanf(%d,&n);for(i=0;i=0;i-)max=0;for(j=i+1;jhj&maxlj) max=lj;li=max+1;printf(%d,l0);5 石子合并在一個圓形操場的四周擺放著n堆石子(n二100),現(xiàn)要將石子有次序地

13、合并成一堆。規(guī)定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數(shù) ,記為該次合并的得分。 編一程序，由文件讀入堆棧數(shù) n 及每 堆棧的石子數(shù) (=20)。選擇一種合并石子的方案 ,使得做 n1 次合并 ,得分的總和最小；輸入數(shù)據(jù)： 第一行為石子堆數(shù) n；第二行為每堆的石子數(shù) ,每兩個數(shù)之間用一個空格分隔。輸出數(shù)據(jù)：從第一至第 n 行為得分最小的合并方案。第 n+1 行是空行 .從第 n+2 行 到第 2n+1 行是得分最大合并方案。每種合并方案用 n 行表示，其中第 i行(1=i=n)表示第i次合并前各堆的石子數(shù)(依順時針次序輸出，哪一 堆先輸出均可 )。要求將待合并的兩堆石子數(shù)以相

14、應(yīng)的負(fù)數(shù)表示。Sample Input44 5 9 4Sample Output4 5 9 48 5 9 13 922 4 5 9 44 14 4 4 18226 最小代價子母樹設(shè)有一排數(shù)，共 n 個，例如： 22 14 7 13 26 15 11。任意 2 個相鄰的數(shù)可 以進(jìn)行歸并， 歸并的代價為該兩個數(shù)的和 ,經(jīng)過不斷的歸并， 最后歸為一 堆，而全部歸并代價的和稱為總代價，給出一種歸并算法，使總代價為最小。輸入、輸出數(shù)據(jù)格式與“石子合并”相同。Sample Input412 5 16 4Sample Output12 5 16 417 16 4 17 20377 商店購物某商店中每種商品都

15、有一個價格。 例如，一朵花的價格是 2 ICU（ICU 是 信息學(xué)競賽的貨幣的單位）；一個花瓶的價格是5 ICU。為了吸引更多的 顧客，商店提供了特殊優(yōu)惠價。特殊優(yōu)惠商品是把一種或幾種商品分成 一組。 并降價銷售。 例如：3朵花的價格不是 6而是 5 ICU； 2個花瓶加 1朵花是 10 ICU 不是 12 ICU。編一個程序， 計算某個顧客所購商品應(yīng)付的費用。 要充分利用優(yōu)惠價以 使顧客付款最小。請注意，你不能變更顧客所購商品的種類及數(shù)量，即 使增加某些商品會使付款總數(shù)減小也不允許你作出任何變更。 假定各種 商品價格用優(yōu)惠價如上所述，并且某顧客購買物品為： 3 朵花和 2個花 瓶。那么顧客應(yīng)

16、付款為 14 ICU 因為：1朵花加 2個花瓶優(yōu)惠價： 10 ICU2 朵花正常價： 4 ICU輸入數(shù)據(jù)：第一個文件 INPUT TXT 描述顧客所購物品（放在購物筐 中） ;第二個文件描述商店提供的優(yōu)惠商品及價格（文件名為OFF ER TXT ）。 兩個文件中都只用整數(shù)。第一個文件INPUT. TXT的格式為：第一行是一個數(shù)字 B （0 B 5）, 表示所購商品種類數(shù)。下面共 B 行，每行中含 3 個數(shù) C，K，P。 C 代 表商品的編碼（每種商品有一個唯一的編碼），1W C 999。K代表該種 商品購買總數(shù)，K K 5。P是該種商品的正常單價（每件商品的價格）， 1 P 999。請注意，購

17、物筐中最多可放 5*5 = 25件商品。第二個文件OFFER. TXT的格式為:第一行是一個數(shù)字 S（0 S9 9）, 表示共有 S 種優(yōu)惠。下面共 S 行,每一行描述一種優(yōu)惠商品的組合中 商品的種類。下面接著是幾個數(shù)字對（C, K）,其中C代表商品編碼， 1 C 9 99。K代表該種商品在此組合中的數(shù)量，1 K 5。本行最后 一個數(shù)字P （1 P 9999）代表此商品組合的優(yōu)惠價。當(dāng)然，優(yōu)惠價 要低于該組合中商品正常價之總和。輸出數(shù)據(jù)：在輸出文件 OUTPUT. TXT 中寫一個數(shù)字（占一行） ,該數(shù) 字表示顧客所購商品（輸入文件指明所購商品）應(yīng)付的最低貨款。8. 旅游預(yù)算 一個旅行社需要估

18、算乘汽車從某城市到另一城市的最小費用, 沿路有若 干加油站,每個加油站收費不一定相同。旅游預(yù)算有如下規(guī)則： 若油箱的油過半,不停車加油,除非油箱中的油不可支持到下一站；每 次加油時都加滿；在一個加油站加油時,司機(jī)要花費 2 元買東西吃；司 機(jī)不必為其他意外情況而準(zhǔn)備額外的油；汽車開出時在起點加滿油箱； 計算精確到分（ 1 元=100 分）。編寫程序估計實際行駛在某路線所需的 最小費用輸入數(shù)據(jù)：從當(dāng)前目錄下的文本文件“route.dat”讀入數(shù)據(jù)。按以下格式輸入若干旅行路線的情況：第一行為起點到終點的距離（實數(shù)） 第二行為三個實數(shù)，后跟一個整數(shù)，每兩個數(shù)據(jù)間用一個空格隔開。其 中第一個數(shù)為汽車油

19、箱的容量（升） ，第二個數(shù)是每升汽油行駛的公里 數(shù)，第三個數(shù)是在起點加滿油箱的費用，第四個數(shù)是加油站的數(shù)量。 （=50）。接下去的每行包括兩個實數(shù)， 每個數(shù)據(jù)之間用一個空格分隔， 其中第一個數(shù)是該加油站離起點的距離， 第二個數(shù)是該加油站每升汽油 的價格（元 /升）。加油站按它們與起點的距離升序排列。所有的輸入都 有一定有解。輸出數(shù)據(jù)：答案輸出到當(dāng)前目錄下的文本文件“route.out”中。該文件包括兩行。第一行為一個實數(shù)和一個整數(shù)，實數(shù)為旅行的最小費用，以元為單位，精確到分，整數(shù)表示途中加油的站的 N。第二行是N個整數(shù), 表示 N 個加油的站的編號， 按升序排列。 數(shù)據(jù)間用一個空格分隔， 此外

20、 沒有多余的空格。Sample Input516.3 38.09 115.7 22.1 20.87 3 2125.4 1.259297.9 1.129345.2 0.999Sample Output38.09 129 皇宮看守太平王世子事件后， 陸小鳳成了皇上特聘的御前一品侍衛(wèi)。 皇宮以午門 為起點，直到后宮嬪妃們的寢宮，呈一棵樹的形狀；某些宮殿間可以互 相望見。大內(nèi)保衛(wèi)森嚴(yán)，三步一崗，五步一哨，每個宮殿都要有人全天 候看守， 在不同的宮殿安排看守所需的費用不同。 可是陸小鳳手上的經(jīng) 費不足，無論如何也沒法在每個宮殿都安置留守侍衛(wèi)。請你編程計算幫助陸小鳳布置侍衛(wèi)，在看守全部宮殿的前提下，使得花

21、 費的經(jīng)費最少。輸入數(shù)據(jù)： 輸入數(shù)據(jù)由文件名為 intput.txt 的文本文件提供。 輸入文件中 數(shù)據(jù)表示一棵樹，描述如下：第 1 行 n ，表示樹中結(jié)點的數(shù)目。第 2 行至第 n+1 行，每行描述每個宮殿結(jié)點信息，依次為：該宮殿結(jié)點標(biāo)號i (0i=n ),在該宮殿安置侍衛(wèi)所需的經(jīng)費 k,該邊的兒子數(shù)m, 接下來 m 個數(shù)，分別是這個節(jié)點的 m 個兒子的標(biāo)號 r1， r2， .， rm。 對于一個 n(0 n = 1500 )個結(jié)點的樹,結(jié)點標(biāo)號在 1到 n 之間,且 標(biāo)號不重復(fù)。輸出數(shù)據(jù)：輸出到 output.txt 文件中。輸出文件僅包含一個數(shù),為所求 的最少的經(jīng)費。如右圖的輸入數(shù)據(jù)示例

22、：Sample Input61 30 3 2 3 42 16 2 5 63 5 04 4 05 11 06 5 0Sample Output25 10 游戲室問題有一個游戲室里有多個游戲室，并且這每個游戲室里還有多個游戲室， 每個游戲室里面還有游戲室， 依此類推。 進(jìn)入每個游戲室都可得到一定 的快樂，每個游戲室的門票價格都大于等于0，都有一個快樂值，并且只有進(jìn)入了一個游戲室， 才可以進(jìn)入它內(nèi)部的游戲室， 小明現(xiàn)在有 n 元 錢，問最大能得到多少的快樂。11 * 基因問題已知兩個基因序列如 s：AGTAGT ；t：ATTAG 。現(xiàn)要你給序列中增加一 些空格后，首先使得兩個序列的長度相等，其次兩個

23、串對應(yīng)符號匹配得 到的值最大。基因只有四種分別用 A 、G、C、T 表示，匹配中不允許兩 個空格相對應(yīng)，任意兩符號的匹配值由下表給出：A G C T A 5 -2 -1 -2 -4G -2 5 -4 -3 -2C -1 -4 5 -5 -1T -2 -3 -5 5 -2 -4 -2 -1 -2提示：定義問題 lij 為取第一個序列的前 i 項，和第二個序列的前 j 項， 這兩個序列加空格匹配的最大值。它的最優(yōu)值與三個子問題有關(guān)， li-1j-1 、lij-1 、li-1j 。建立遞歸公式如下：其中 m0tj 表示表中空格和 tj 匹配的對應(yīng)值。 思考：本問題的初始化。12 * 田忌賽馬田忌與齊王賽馬，雙方各有 n匹馬參賽（n=100）,每場比賽賭注為1 兩黃金， 現(xiàn)已知齊王與田忌的每匹馬的速度， 并且齊王肯定是按馬的速 度從快到慢出場， 現(xiàn)要你寫一個程序幫助田忌計