動(dòng)態(tài)規(guī)劃II含詳細(xì)c語言代碼

1、第十課動(dòng)態(tài)規(guī)劃(II)綜合實(shí)踐考核最長(zhǎng)公共子序列 1、問題描述 我們稱序列Z = 是序列X = 的子序列當(dāng)且僅當(dāng)存在嚴(yán)格上升的序列，使得對(duì)j = 1, 2, . ,k, 有xij = zj。比如Z = 是X = 的子序列?，F(xiàn)在給出兩個(gè)序列X 和Y，你的任務(wù)是找到X 和Y 的最大公共子序列，也就是說要找到一個(gè)最長(zhǎng)的序列Z，使得Z 既是X 的子序列也是Y 的子序列。輸入數(shù)據(jù)輸入包括多組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)包括一行，給出兩個(gè)長(zhǎng)度不超過200 的字符串，表示兩個(gè)序列。兩個(gè)字符串之間由若干個(gè)空格隔開。問題描述 輸出要求 對(duì)每組輸入數(shù)據(jù)，輸出一行，給出兩個(gè)序列的最大公共子序列的長(zhǎng)度。 輸入樣例 abcfbc

2、 abfcab programming contest abcd mnp 輸出樣例 4 2 02、解題思路 用字符數(shù)組s1、s2存放兩個(gè)字符串，用s1i表示s1中的第i 個(gè)字符，s2j表示s2中的第j個(gè)字符（字符編號(hào)從1 開始），用s1i表示s1的前i個(gè)字符所構(gòu)成的子串，s2j表示s2的前j個(gè)字符構(gòu)成的子串，MaxLen(i,j)表示s1i 和s2j 的最長(zhǎng)公共子序列的長(zhǎng)度，那么遞推關(guān)系如下：if( i =0 | j = 0 ) MaxLen(i, j) = 0 /兩個(gè)空串的最長(zhǎng)公共子序列長(zhǎng)度是0else if( s1i = s2j ) MaxLen(i, j) = MaxLen(i-1, j

3、-1 ) + 1;else MaxLen(i,j) = Max(MaxLen(i, j-1), MaxLen(i-1, j);2、解題思路 顯然本題目的“狀態(tài)”就是s1 中的位置i 和s2 中的位置j。 “值”就是MaxLen(i, j)。 狀態(tài)的數(shù)目是s1 長(zhǎng)度和s2 長(zhǎng)度的乘積?？梢杂靡粋€(gè)二維數(shù)組來存儲(chǔ)各個(gè)狀態(tài)下的“值”。 本問題的兩個(gè)子問題，和原問題形式完全一致的，只不過規(guī)模小了一點(diǎn)。3、參考程序#include #include #define MAX_LEN 1000char sz1MAX_LEN;char sz2MAX_LEN;int aMaxLenMAX_LENMAX_LEN;i

4、nt main(void) while( scanf(%s%s, sz1+1 ,sz2+1 ) 0 ) int nLength1 = strlen( sz1+1); int nLength2 = strlen( sz2+1); int i, j; for( i = 0;i = nLength1; i + ) aMaxLeni0 = 0; for( j = 0;j = nLength2; j + ) aMaxLen0j = 0;3、參考程序 for( i = 1;i = nLength1;i + ) for( j = 1; j nLen2 ) aMaxLenij = nLen1; else aM

5、axLenij = nLen2; printf(%dn, aMaxLennLength1nLength2); return 0;陪審團(tuán)的人選 1、問題描述 在遙遠(yuǎn)的國(guó)家佛羅布尼亞，嫌犯是否有罪，須由陪審團(tuán)決定。陪審團(tuán)是由法官從公眾中挑選的。先隨機(jī)挑選n 個(gè)人作為陪審團(tuán)的候選人，然后再從這n 個(gè)人中選m 人組成陪審團(tuán)。選m 人的辦法是： 控方和辯方會(huì)根據(jù)對(duì)候選人的喜歡程度，給所有候選人打分，分值從0 到20。為了公平起見，法官選出陪審團(tuán)的原則是：選出的m 個(gè)人，必須滿足辯方總分和控方總分的差的絕對(duì)值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對(duì)值相同，那么選辯控雙方總分之和最大的方案即

6、可。最終選出的方案稱為陪審團(tuán)方案。問題描述輸入數(shù)據(jù)輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)的第一行是兩個(gè)整數(shù)n 和m，n 是候選人數(shù)目，m 是陪審團(tuán)人數(shù)。注意，1=n=200, 1=m=20 而且 m=n。接下來的n 行，每行表示一個(gè)候選人的信息，它包含2 個(gè)整數(shù)，先后是控方和辯方對(duì)該候選人的打分。候選人按出現(xiàn)的先后從1開始編號(hào)。兩組有效數(shù)據(jù)之間以空行分隔。最后一組數(shù)據(jù)n=m=0輸出要求對(duì)每組數(shù)據(jù)，先輸出一行，表示答案所屬的組號(hào), 如 Jury #1, Jury #2, 等。接下來的一行要象例子那樣輸出陪審團(tuán)的控方總分和辯方總分。再下來一行要以升序輸出陪審團(tuán)里每個(gè)成員的編號(hào)，兩個(gè)成員編號(hào)之間用空格分隔。每組

7、輸出數(shù)據(jù)須以一個(gè)空行結(jié)束。問題描述輸入樣例4 21 22 34 16 20 0輸出樣例Jury #1Best jury has value 6 for prosecution and value 4 for defence:2 32、解題思路 為敘述方便，將任一選擇方案中，辯方總分和控方總分之差簡(jiǎn)稱為“辯控差”，辯方總分和控方總分之和稱為“辯控和”。第i 個(gè)候選人的辯方總分和控方總分之差記為V(i)，辯方總分和控方總分之和記為S(i)?，F(xiàn)用f(j, k)表示，取j 個(gè)候選人，使其辯控差為k 的所有方案中，辯控和最大的那個(gè)方案（該方案稱為“方案f(j, k)”）的辯控和。并且，我們還規(guī)定，如果沒

8、法選j 個(gè)人，使其辯控差為k，那么f(j, k)的值就為-1，也稱方案f(j, k)不可行。本題是要求選出m 個(gè)人，那么，如果對(duì)k 的所有可能的取值，求出了所有的f(m, k) (-20m k 20m)，那么陪審團(tuán)方案自然就很容易找到了。2、解題思路 問題的關(guān)鍵是建立遞推關(guān)系。顯然，方案f(j, k)是由某個(gè)可行的方案f(j-1, x)( -20m x 20m)演化而來的?？尚蟹桨竑(j-1, x)能演化成方案f(j, k)的必要條件是：存在某個(gè)候選人i，i 在方案f(j-1, x)中沒有被選上，且x+V(i) = k。在所有滿足該必要條件的f(j-1, x)中，選出 f(j-1, x) +

9、S(i) 的值最大的那個(gè)，那么方案f(j-1, x)再加上候選人i，就演變成了方案 f(j, k)。由上面知一個(gè)方案都選了哪些人需要全部記錄下來。不妨將方案f(j, k)中最后選的那個(gè)候選人的編號(hào)，記在二維數(shù)組的元素pathjk中。那么方案f(j, k)的倒數(shù)第二個(gè)人選的編號(hào)，就是pathj-1k-Vpathjk。假定最后算出了方案的辯控差是k，那么從pathmk出發(fā)，就能順藤摸瓜一步步求出所有被選中的候選人。2、解題思路 初始條件，只能確定f(0, 0) = 0。由此出發(fā)，一步步自底向上遞推，就能求出所有的可行方案f(m, k)( -20m k 20m)。實(shí)際解題的時(shí)候，會(huì)用一個(gè)二維數(shù)組f

10、來存放f(j, k)的值。而且，由于題目中辯控差的值k 可以為負(fù)數(shù)，而程序中數(shù)租下標(biāo)不能為負(fù)數(shù)，所以，在程序中不妨將辯控差的值都加上20m，以免下標(biāo)為負(fù)數(shù)導(dǎo)致出錯(cuò)，即題目描述中，如果辯控差為0，則在程序中辯控差為20m。3、參考程序#include #include #include int f301000;int Path301000;int P300; /控方打分int D300; /辯方打分int Answer30; /存放最終方案的人選int CompareInt(const void * e1, const void * e2) return * (int *) e1) - * (i

11、nt *) e2);3、參考程序int main(void) int i, j, k; int t1, t2; int n, m; int nMinP_D; /辯控雙方總分一樣時(shí)的辯控差 int nCaseNo;/測(cè)試數(shù)據(jù)編號(hào) nCaseNo=0; scanf(%d%d, &n, &m); while(n+m) nCaseNo+; for(i=1;i=n;i+) scanf(%d%d, &Pi, &Di); memset(f, -1, sizeof(f); memset(Path, 0, sizeof(Path); nMinP_D=m*20; /題目中的辯控差為0 /對(duì)應(yīng)到程序中辯控差就是m*

12、20 f0nMinP_D=0; /選0 個(gè)人辯控差為0 的方案，其辯控和就是03、參考程序 for(j=0;jm;j+) /每次循環(huán)選出第j 個(gè)人，共要選出m 人 for(k=0;k=0) /方案 f(j, k)可行 for(i=1;ifj+1k+Pi-Di) /即時(shí)判別記住更合適的f(j,k) t1=j; t2=k; while(t10&Patht1t2!=i) /t2減去編號(hào)為Patht1t2的辯控差 t2-=PPatht1t2-DPatht1t2; t1-;/減少1人 if(t1=0) /沒有發(fā)現(xiàn) fj+1k+Pi-Di=fjk+Pi+Di; Pathj+1k+Pi-Di=i; 3、參考

13、程序 i=nMinP_D; j=0; while(fmi+j0&fmi-jfmi-j)/絕對(duì)值相同時(shí)找辯控和最大的 k=i+j; else k=i-j; printf(Jury #%dn, nCaseNo); printf(Best jury has value %d for prosecution and value %d for defence:n, (k-nMinP_D+fmk)/2, (fmk-k+nMinP_D)/2); for(i=1;i=m;i+) Answeri=Pathm-i+1k; k-=PAnsweri-DAnsweri;/減去辯控差 qsort(Answer+1, m,

14、 sizeof(int), CompareInt); for(i=1;i=m;i+) printf( %d, Answeri); printf(n); printf(n); scanf(%d%d, &n, &m); return 0;購物問題 1、問題描述 由于換季，ACM商場(chǎng)推出優(yōu)惠活動(dòng)，以超低價(jià)格出售若干種商品。但是，商場(chǎng)為避免過分虧本，規(guī)定某些商品不能同時(shí)購買，而且每種超低價(jià)商品只能買一件。身為顧客的你想獲得最大的實(shí)惠，也就是爭(zhēng)取節(jié)省最多的錢。經(jīng)過仔細(xì)研究過，我們發(fā)現(xiàn)，商場(chǎng)出售的超低價(jià)商品中，不存在以下這種情況：N(3=n)種商品C1,C2,Cn，其中Ci和Ci+1是不能同時(shí)購買的(i=

15、1,2,n-1)，而且C1和Cn也不能同時(shí)購買。請(qǐng)編程計(jì)算可以節(jié)省的最大金額數(shù)。問題描述輸入數(shù)據(jù)第1行兩個(gè)整數(shù)K,M(1=k=1000)，其中K表示超低價(jià)商品數(shù)，K種商品的編號(hào)依次為1,2,K；M表示不能同時(shí)購買的商品對(duì)數(shù)。接下來K行，第i行有一個(gè)整數(shù)Xi表示購買編號(hào)為i的商品可以節(jié)省的金額(1=Xi=100)。再接下來M行，每行兩個(gè)數(shù)A和B，表示A和B不能同時(shí)購買，1=A=K，1=B=K，AB。 輸出要求僅一個(gè)整數(shù)，表示能節(jié)省的最大金額數(shù)。問題描述輸入樣例3 11111 2輸出樣例22、解題思路 本題關(guān)鍵是構(gòu)造一個(gè)結(jié)點(diǎn)帶權(quán)的圖，結(jié)點(diǎn)表示超低價(jià)商品，結(jié)點(diǎn)的權(quán)值表示購買該商品能節(jié)省的金額，邊表示

16、邊所連的兩個(gè)點(diǎn)的商品不能同時(shí)購買。這樣就相當(dāng)于在圖中找出一個(gè)點(diǎn)集，使該點(diǎn)集中任兩點(diǎn)沒有連邊而且權(quán)值之和最大。 依題意，該圖是無環(huán)圖，所以該圖由若干棵樹組成。只要把每棵樹的相應(yīng)最大節(jié)省金額求出來再求和即得結(jié)果。2、解題思路 對(duì)于單棵樹，可以用動(dòng)態(tài)規(guī)劃的方法求出結(jié)果，方法如下： (1)對(duì)該棵樹廣度或深度遍歷生成相應(yīng)的有向樹；(2)對(duì)樹中每個(gè)結(jié)點(diǎn)定義兩個(gè)函數(shù)F(i)和G(i)，分別表示以i為根的子樹中選擇i和不選擇i時(shí)，該子樹的最大節(jié)省金額數(shù)。另外S(i)表示結(jié)點(diǎn)i權(quán)值。動(dòng)態(tài)規(guī)劃方法為： 對(duì)葉子結(jié)點(diǎn)：F(i)=S(i), G(i)=0 對(duì)非葉子結(jié)點(diǎn)：F(i)=sum(G(j)+S(i), G(i)=

17、sum(max(F(j),G(j)其中j為i的子女，sum表示對(duì)各個(gè)子樹求和。(3)若該樹的根為r，則該樹的結(jié)果為max(F(r),G(r)。3、參考程序#include#includeusing namespace std;int k, s1001;/商品種類與其節(jié)省金額struct node /圖結(jié)點(diǎn)定義 node(int vv=0, node* nn=NULL) v=vv; next=nn; int v; node *next; *g1001;/gi表示第i個(gè)結(jié)點(diǎn)相鄰的結(jié)點(diǎn)組成的鏈表int tag1001;/標(biāo)記結(jié)點(diǎn)是否搜索過沒有,1表示已搜索，0則沒有int funf1001, fun

18、g1001;/深度優(yōu)先遍歷該樹并生成相應(yīng)的有根樹void search(int v);/搜索出以v為根生成的有根樹int getf(int v);/計(jì)算以v為根的子樹中選擇v時(shí)，該子樹的最大節(jié)省金額數(shù)int getg(int v);/計(jì)算以v為根的子樹中不選擇v時(shí)，該子樹的最大節(jié)省金額數(shù)3、參考程序int main(void) int m, i, v1, v2; int ans = 0; memset(g, 0, sizeof(g);/每個(gè)指針初始化為NULL memset(tag, 0, sizeof(tag); memset(funf,-1,sizeof(funf); memset(fun

19、g,-1,sizeof(fung); cin k m;/讀入商品種類與不能同時(shí)購買商品對(duì)數(shù) for(i=1; i si; for(i=1; i v1 v2; gv1=new node(v2,gv1);/以插入形成鄰接表 gv2=new node(v1,gv2); 3、參考程序 /對(duì)每個(gè)還沒有被訪問的結(jié)點(diǎn)，以該結(jié)點(diǎn)為根生成相應(yīng)的有根樹，對(duì) /該樹用動(dòng)態(tài)規(guī)劃的方法求解目標(biāo)函數(shù)，并累加起來作為最終答案 for(i=1; i getg(i) ? getf(i) : getg(i); cout next)/對(duì)子女依次循環(huán) if(tagloop-v = 0)/該子女沒有訪問過 node *pre=NULL, *