動態(tài)規(guī)劃I(含詳細c語言代碼)

第九課動態(tài)規(guī)劃(I)綜合實踐考核數(shù)字三角形1、問題描述上圖給出了一個數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。對于每條路徑，把路徑上面的數(shù)加起來可以得到一個和，和最大的路徑稱為最佳路徑。你的任務(wù)就是求出最佳路徑上的數(shù)字之和。注意：路徑上的每一步只能從一個數(shù)走到下一層上和它最近的左邊的數(shù)或者右邊的數(shù)。問題描述輸入數(shù)據(jù)輸入的第一行是一個整數(shù)N(1<N<=100)，給出三角形的行數(shù)。下面的N行給出數(shù)字三角形。數(shù)字三角形上的數(shù)的范圍都在0和100之間。輸出要求輸出最大的和。問題描述輸入樣例5738810274445265輸出樣例302、解題思路這道題目可以用遞歸的方法解決。基本思路是：以D(r,j)表示第r行第j個數(shù)字(r，j都從1開始算)，以MaxSum(r,j)代表從第r行的第j個數(shù)字到底邊的最佳路徑的數(shù)字之和，則本題是要求MaxSum(1,1)。從某個D(r,j)出發(fā)，顯然下一步只能走D(r+1,j)或者D(r+1,j+1)。如果走D(r+1,j)，那么得到的MaxSum(r,j)就是MaxSum(r+1,j)+D(r,j)；如果走D(r+1,j+1)，那么得到的MaxSum(r,j)就是MaxSum(r+1,j+1)+D(r,j)。所以，選擇往哪里走，就看MaxSum(r+1,j)和MaxSum(r+1,j+1)哪個更大了。3、參考程序I#include<stdio.h>#defineMAX_NUM100intD[MAX_NUM+10][MAX_NUM+10];intN;intMaxSum(intr,intj){ if(r==N) returnD[r][j]; intnSum1=MaxSum(r+1,j); intnSum2=MaxSum(r+1,j+1); if(nSum1>nSum2) returnnSum1+D[r][j]; returnnSum2+D[r][j];}3、參考程序Iintmain(void){ intm; scanf("%d",&N); for(inti=1;i<=N;i++) for(intj=1;j<=i;j++) scanf("%d",&D[i][j]); printf("%d",MaxSum(1,1)); return0;}提交結(jié)果：TimeLimitExceed程序I分析上面的程序，效率非常低，在N值并不大，比如N=100的時候，就慢得幾乎永遠算不出結(jié)果了。為什么會這樣呢？是因為過多的重復計算。我們不妨將對MaxSum函數(shù)的一次調(diào)用稱為一次計算。那么，每次計算MaxSum(r,j)的時候，都要計算一次MaxSum(r+1,j+1)，而每次計算MaxSum(r,j+1)的時候，也要計算一次MaxSum(r+1,j+1)。重復計算因此產(chǎn)生。在題目中給出的例子里，如果我們將MaxSum(r,j)被計算的次數(shù)都寫在位置（r,j），那么就能得到右面的三角形：111121133114641738810274445265程序分析從上圖可以看出，最后一行的計算次數(shù)總和是16，倒數(shù)第二行的計算次數(shù)總和是8。不難總結(jié)出規(guī)律，對于N行的三角形，總的計算次數(shù)是2^0+2^1+2^2+…+2^(N-1)=2^N-1。當N=100時，總的計算次數(shù)是一個讓人無法接受的大數(shù)字。既然問題出在重復計算，那么解決的辦法，當然就是，一個值一旦算出來，就要記住，以后不必重新計算。即第一次算出MaxSum(r,j)的值時，就將該值存放起來，下次再需要計算MaxSum(r,j)時，直接取用存好的值即可，不必再次調(diào)用MaxSum

進行函數(shù)遞歸計算了。這樣，每個MaxSum(r,j)都只需要計算1次即可，那么總的計算次數(shù)（即調(diào)用MaxSum

函數(shù)的次數(shù)）就是三角形中的數(shù)字總數(shù)，即1+2+3+…+N=N(N+1)/2。如何存放計算出來的MaxSum（r,j）值呢？顯然，用一個二維數(shù)組aMaxSum[N][N]就能解決。aMaxSum[r][j]就存放MaxSum(r,j)的計算結(jié)果。下次再需要MaxSum(r,j)的值時，不必再調(diào)用MaxSum

函數(shù)，只需直接取aMaxSum[r][j]的值即可。4、參考程序II#include<stdio.h>#include<memory.h>#defineMAX_NUM100intD[MAX_NUM+10][MAX_NUM+10];intN;intaMaxSum[MAX_NUM+10][MAX_NUM+10];intMaxSum(intr,intj){if(r==N)returnD[r][j];if(aMaxSum[r+1][j]==-1)//如果MaxSum(r+1,j)沒有計算過aMaxSum[r+1][j]=MaxSum(r+1,j);if(aMaxSum[r+1][j+1]==-1)aMaxSum[r+1][j+1]=MaxSum(r+1,j+1);if(aMaxSum[r+1][j]>aMaxSum[r+1][j+1])returnaMaxSum[r+1][j]+D[r][j];returnaMaxSum[r+1][j+1]+D[r][j];}4、參考程序IIintmain(void){intm;scanf("%d",&N);//將aMaxSum全部置成-1,開始時所有的MaxSum(r,j)都沒有算過memset(aMaxSum,-1,sizeof(aMaxSum));for(inti=1;i<=N;i++)for(intj=1;j<=i;j++)scanf("%d",&D[i][j]);printf("%d",MaxSum(1,1));return0;}程序II分析這種將一個問題分解為子問題遞歸求解，并且將中間結(jié)果保存以避免重復計算的辦法，就叫做“動態(tài)規(guī)劃”。動態(tài)規(guī)劃通常用來求最優(yōu)解，能用動態(tài)規(guī)劃解決的求最優(yōu)解問題，必須滿足，最優(yōu)解的每個局部解也都是最優(yōu)的。以上題為例，最佳路徑上面的每個數(shù)字到底部的那一段路徑，都是從該數(shù)字出發(fā)到達到底部的最佳路徑。實際上，遞歸的思想在編程時未必要實現(xiàn)為遞歸函數(shù)。在上面的例子里，有遞推公式：因此，不需要寫遞歸函數(shù)，從aMaxSum[N-1]這一行元素開始向上逐行遞推，就能求得aMaxSum[1][1]的值了。5、參考程序IIIintD[MAX_NUM+10][MAX_NUM+10];intN;intaMaxSum[MAX_NUM+10][MAX_NUM+10];intmain(void){inti,j;scanf("%d",&N);for(i=1;i<=N;i++)for(j=1;j<=i;j++)scanf("%d",&D[i][j]);for(j=1;j<=N;j++)aMaxSum[N][j]=D[N][j];for(i=N;i>1;i--)for(j=1;j<i;j++){if(aMaxSum[i][j]>aMaxSum[i][j+1])aMaxSum[i-1][j]=aMaxSum[i][j]+D[i-1][j];elseaMaxSum[i-1][j]=aMaxSum[i][j+1]+D[i-1][j];}printf("%d",aMaxSum[1][1]);return0;}思考題：上面的幾個程序只算出了最佳路徑的數(shù)字之和。如果要求輸出最佳路徑上的每個數(shù)字，該怎么辦？動態(tài)規(guī)劃解題的一般思路許多求最優(yōu)解的問題可以用動態(tài)規(guī)劃來解決。首先要把原問題分解為若干個子問題。注意單純的遞歸往往會導致子問題被重復計算，用動態(tài)規(guī)劃的方法，子問題的解一旦求出就要被保存，所以每個子問題只需求解一次。子問題經(jīng)常和原問題形式相似，有時甚至完全一樣，只不過規(guī)模從原來的n變成了n-1，或從原來的n×m

變成了n×(m-1)……等等。找到子問題，就意味著找到了將整個問題逐漸分解的辦法。分解下去，直到最底層規(guī)模最小的的子問題可以一目了然地看出解。每一層子問題的解決，會導致上一層子問題的解決，逐層向上，就會導致最終整個問題的解決。如果從最底層的子問題開始，自底向上地推導出一個個子問題的解，那么編程的時候就不需要寫遞歸函數(shù)。動態(tài)規(guī)劃解題的一般思路用動態(tài)規(guī)劃解題時，將和子問題相關(guān)的各個變量的一組取值，稱之為一個“狀態(tài)”。一個“狀態(tài)”對應(yīng)于一個或多個子問題，所謂某個“狀態(tài)”下的“值”，就是這個“狀態(tài)”所對應(yīng)的子問題的解。比如數(shù)字三角形，子問題就是“從位于(r，j)數(shù)字開始，到底邊路徑的最大和”。這個子問題和兩個變量r和j相關(guān)，那么一個“狀態(tài)”，就是r,j的一組取值，即每個數(shù)字的位置就是一個“狀態(tài)”。該“狀態(tài)”所對應(yīng)的“值”，就是從該位置的數(shù)字開始，到底邊的最佳路徑上的數(shù)字之和。定義出什么是“狀態(tài)”，以及在該“狀態(tài)”下的“值”后，就要找出不同的狀態(tài)之間如何遷移――即如何從一個或多個“值”已知的“狀態(tài)”，求出另一個“狀態(tài)”的“值”。狀態(tài)的遷移可以用遞推公式表示，此遞推公式也可被稱作“狀態(tài)轉(zhuǎn)移方程”。動態(tài)規(guī)劃解題的一般思路用動態(tài)規(guī)劃解題，如何尋找“子問題”，定義“狀態(tài)”，“狀態(tài)轉(zhuǎn)移方程”是什么樣的，并沒有一定之規(guī)，需要具體問題具體分析，題目做多了就會有感覺。甚至，對于同一個問題，分解成子問題的辦法可能不止一種，因而“狀態(tài)”也可以有不同的定義方法。不同的“狀態(tài)”定義方法可能會導致時間、空間效率上的區(qū)別。最長上升子序列1、問題描述一個數(shù)的序列bi，當b1<b2<...<bS的時候，我們稱這個序列是上升的。對于給定的一個序列(a1,a2,...,aN)，我們可以得到一些上升的子序列(ai1,ai2,...,aiK)，這里1<=i1<i2<...<iK<=N。比如，對于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。這些子序列中最長的長度是4，比如子序列(1,3,5,8).你的任務(wù)，就是對于給定的序列，求出最長上升子序列的長度。問題描述輸入數(shù)據(jù)輸入的第一行是序列的長度N(1<=N<=1000)。第二行給出序列中的N個整數(shù)，這些整數(shù)的取值范圍都在0到10000。輸出要求最長上升子序列的長度。輸入樣例71735948輸出樣例42、解題思路如何把這個問題分解成子問題呢？經(jīng)過分析，發(fā)現(xiàn)“求以ak（k=1,2,3…N）為終點的最長上升子序列的長度”是個好的子問題――這里把一個上升子序列中最右邊的那個數(shù)，稱為該子序列的“終點”。雖然這個子問題和原問題形式上并不完全一樣，但是只要這N個子問題都解決了，那么這N個子問題的解中，最大的那個就是整個問題的解。由上所述的子問題只和一個變量相關(guān)，就是數(shù)字的位置。因此序列中數(shù)的位置k就是“狀態(tài)”，而狀態(tài)k對應(yīng)的“值”，就是以ak

做為“終點”的最長上升子序列的長度。這個問題的狀態(tài)一共有N個。狀態(tài)定義出來后，轉(zhuǎn)移方程就不難想了。2、解題思路假定MaxLen(k)表示以ak

做為“終點”的最長上升子序列的長度，那么：MaxLen(1)=1MaxLen(k)=Max{MaxLen(i)：1<i<k且

ai<ak

且

k≠1}+1這個狀態(tài)轉(zhuǎn)移方程的意思就是，MaxLen(k)的值，就是在ak

左邊，“終點”數(shù)值小于ak，且長度最大的那個上升子序列的長度再加1。因為ak

左邊任何“終點”小于ak

的子序列，加上ak

后就能形成一個更長的上升子序列。實際實現(xiàn)的時候，可以不必編寫遞歸函數(shù)，因為從

MaxLen(1)就能推算出MaxLen(2)，有了MaxLen(1)和MaxLen(2)就能推算出MaxLen(3)……3、參考程序intb[MAX_N+10];intaMaxLen[MAX_N+10];intmain(void){inti,j,N;scanf("%d",&N);for(i=1;i<=N;i++)scanf("%d",&b[i]);aMaxLen[1]=1;3、參考程序for(i=2;i<=N;i++){//求以第i個數(shù)為終點的最長上升子序列的長度

intnTmp=0;//記錄第i個數(shù)左邊子序列最大長度

for(j=1;j<i;j++){//搜索以第i個數(shù)左邊數(shù)為終點的最長上升子序列長度

if(b[i]>b[j]){if(nTmp<aMaxLen[j])nTmp=aMaxLen[j];}}aMaxLen[i]=nTmp+1;}intnMax=-1;for(i=1;i<=N;i++)if(nMax<aMaxLen[i])nMax=aMaxLen[i];printf("%d\n",nMax);return0;}思考題：改進此程序，使之能夠輸出最長上升子序列HelpJimmy1、問題描述"HelpJimmy"是在下圖所示的場景上完成的游戲：問題描述場景中包括多個長度和高度各不相同的平臺。地面是最低的平臺，高度為零，長度無限。Jimmy老鼠在時刻0從高于所有平臺的某處開始下落，它的下落速度始終為1米/秒。當Jimmy落到某個平臺上時，游戲者選擇讓它向左還是向右跑，它跑動的速度也是1米/秒。當Jimmy跑到平臺的邊緣時，開始繼續(xù)下落。Jimmy每次下落的高度不能超過MAX米，不然就會摔死，游戲也會結(jié)束。設(shè)計一個程序，計算Jimmy到地面時可能的最早時間。問題描述輸入數(shù)據(jù)第一行是測試數(shù)據(jù)的組數(shù)t（0<=t<=20）。每組測試數(shù)據(jù)的第一行是四個整數(shù)N，X，Y，MAX，用空格分隔。N是平臺的數(shù)目（不包括地面），X和Y是Jimmy開始下落的位置的橫豎坐標，MAX是一次下落的最大高度。接下來的N行每行描述一個平臺，包括三個整數(shù)，X1[i]，X2[i]和H[i]。H[i]表示平臺的高度，X1[i]和X2[i]表示平臺左右端點的橫坐標。1<=N<=1000，-20000<=X,X1[i],X2[i]<=20000，0<H[i]<Y<=20000（i=1..N）。所有坐標的單位都是米。Jimmy的大小和平臺的厚度均忽略不計。如果Jimmy恰好落在某個平臺的邊緣，被視為落在平臺上。所有的平臺均不重疊或相連。測試數(shù)據(jù)保Jimmy一定能安全到達地面。問題描述輸出要求對輸入的每組測試數(shù)據(jù)，輸出一個整數(shù)，Jimmy到地面時可能的最早時間。輸入樣例13817200108010134143輸出樣例232、解題思路此題目的“子問題”是什么呢？Jimmy跳到一塊板上后，可以有兩種選擇，向左走或向右走。走到左端和走到右端所需的時間，容易算出。如果我們能知道，以左端為起點到達地面的最短時間，和以右端為起點到達地面的最短時間，那么向左走還是向右走，就很容選擇了。因此，整個問題就被分解成兩個子問題，即Jimmy所在位置下方第一塊板左端為起點到地面的最短時間，和右端為起點到地面的最短時間。這兩個子問題在形式上和原問題是完全一致的。將板子從上到下從1開始進行無重復的編號(高度相同的板子，哪塊編號在前無所謂)，那么，和上面兩個子問題相關(guān)的變量就只有板子的編號。2、解題思路所以，本題目的“狀態(tài)”就是板子編號，而一個“狀態(tài)”對應(yīng)的“值”有兩部分，是兩個子問題的解，即從該板子左端出發(fā)到達地面的最短時間，和從該板子右端出發(fā)到達地面的最短時間。不妨認為Jimmy開始的位置是一個編號為0，長度為0的板子，假設(shè)LeftMinTime(k)表示從k號板子左端到地面的最短時間，RightMinTime(k)表示從k號板子右端到地面的最短時間，那么，求板子k左端點到地面的最短時間的方法如下：if(板子k左端正下方?jīng)]有別的板子){if(板子k的高度h(k)大于Max)

LeftMinTime(k)=∞;else

LeftMinTime(k)=h(k);}elseif(板子k左端正下方的板子編號是m)

LeftMinTime(k)=h(k)-h(m)+

Min(LeftMinTime(m)+Lx(k)-Lx(m),

RightMinTime(m)+Rx(m)-Lx(k));

2、解題思路上面，h(i)就代表i號板子的高度，Lx(i)就代表i號板子左端點的橫坐標，Rx(i)就代表i號板子右端點的橫坐標。那么h(k)-h(m)當然就是從k號板子跳到m號板子所需要的時間，Lx(k)-Lx(m)就是從m號板子的落腳點走到m號板子左端點的時間，Rx(m)-Lx(k)就是從m號板子的落腳點走到右端點所需的時間。求RightMinTime(k)的過程類似。不妨認為Jimmy開始的位置是一個編號為0，長度為0的板子，那么整個問題就是要求LeftMinTime(0)。輸入數(shù)據(jù)中，板子并沒有按高度排序，所以程序中一定要首先將板子排序。3、參考程序#include<stdio.h>#include<memory.h>#include<stdlib.h>#defineMAX_N1000#defineINFINITE1000000intt,n,x,y,max;structPlatform{intLx,Rx,h;};PlatformaPlatform[MAX_N+10];intaLeftMinTime[MAX_N+10];intaRightMinTime[MAX_N+10];intMyCompare(constvoid*e1,constvoid*e2){Platform*p1,*p2;p1=(Platform*)e1;p2=(Platform*)e2;returnp2->h-p1->h;//從大到小排列}3、參考程序intMinTime(intL,boolbLeft){inty=aPlatform[L].h;inti,x;if(bLeft)x=aPlatform[L].Lx;elsex=aPlatform[L].Rx;for(i=L+1;i<=n;i++)//找到下一張板子

{if(aPlatform[i].Lx<=x&&aPlatform[i].Rx>=x)break;}if(i<=n)//找到了

{if(y-aPlatform[i].h>max)//太高

returnINFINITE;}3、參考程序else//沒找到

{if(y>max)//離地面太高

returnINFINITE;elsereturny;}//特殊情況處理完畢

intnLeftTime=y-aPlatform[i].h+x-aPlatform[i].Lx;intnRightTime=y-aPlatform[i].h+aPlatform[i].Rx-x;if(aLeftMinTime[i]==-1)//還沒有存儲值

aLeftMinTime[i]=MinTime(i,true);if(aRightMinTime[i]==-1)aRightMinTime[i]=MinTime(i,false);nLeftTime+=aLeftMinTime[i];nRightTime+=aRightMinTime[i];if(nLeftTime<nRightTime)returnnLeftTime;returnnRightTime;}3、參考程序intmain(void){scanf("%d",&t);for(inti=0;i<t;i++){memset(aLeftMinTime,-1,sizeof(aLeftMinTime));memset(aRightMinTime,-1,sizeof(aRightMinTime));scanf("%d%d%d%d",&n,&x,&y,&max);aPlatform[0].Lx=x;aPlatform[0].Rx=x;//長度為0的板子aPlatform[0].h=y;for(intj=1;j<=n;j++)scanf("%d%d%d",&aPlatform[j].Lx,

&aPlatform[j].Rx,&aPlatform[j].h);qsort(aPlatform,n+1,sizeof(Platform),MyCompare);printf("%d\n",MinTime(0,true));}return0;}思考題：重新編寫此程序，要求不使用遞歸函數(shù)最長公共子序列1、問題描述我們稱序列Z=<z1,z2,...,zk>是序列X=<x1,x2,...,xm>的子序列當且僅當存在嚴格上升的序列<i1,i2,...,ik>，使得對j=1,2,...,k,有xij=zj。比如Z=<a,b,f,c>是X=<a,b,c,f,b,c>的子序列。現(xiàn)在給出兩個序列X和Y，你的任務(wù)是找到X和Y的最大公共子序列，也就是說要找到一個最長的序列Z，使得Z既是X的子序列也是Y的子序列。輸入數(shù)據(jù)輸入包括多組測試數(shù)據(jù)。每組數(shù)據(jù)包括一行，給出兩個長度不超過200的字符串，表示兩個序列。兩個字符串之間由若干個空格隔開。問題描述輸出要求對每組輸入數(shù)據(jù)，輸出一行，給出兩個序列的最大公共子序列的長度。輸入樣例

abcfbc

abfcabprogrammingcontest

abcd

mnp輸出樣例4202、解題思路用字符數(shù)組s1、s2存放兩個字符串，用s1[i]表示s1中的第i個字符，s2[j]表示s2中的第j個字符（字符編號從1開始），用s1i表示s1的前i個字符所構(gòu)成的子串，s2j表示s2的前j個字符構(gòu)成的子串，MaxLen(i,j)表示s1i

和s2j

的最長公共子序列的長度，那么遞推關(guān)系如下：if(i==0||j==0)

MaxLen(i,j)=0//兩個空串的最長公共子序列長度是0elseif(s1[i]==s2[j])

MaxLen(i,j)=MaxLen(i-1,j-1)+1;else

MaxLen(i,j)=Max(MaxLen(i,j-1),MaxLen(i-1,j));2、解題思路顯然本題目的“狀態(tài)”就是s1中的位置i和s2中的位置j?！爸怠本褪荕axLen(i,j)。狀態(tài)的數(shù)目是s1長度和s2長度的乘積?？梢杂靡粋€二維數(shù)組來存儲各個狀態(tài)下的“值”。本問題的兩個子問題，和原問題形式完全一致的，只不過規(guī)模小了一點。3、參考程序#include<stdio.h>#include<string.h>#defineMAX_LEN1000charsz1[MAX_LEN];charsz2[MAX_LEN];intaMaxLen[MAX_LEN][MAX_LEN];intmain(void){while(scanf("%s%s",sz1+1,sz2+1)>0){intnLength1=strlen(sz1+1);intnLength2=strlen(sz2+1);inti,j;for(i=0;i<=nLength1;i++)aMaxLen[i][0]=0;for(j=0;j<=nLength2;j++)aMaxLen[0][j]=0;3、參考程序

for(i=1;i<=nLength1;i++){for(j=1;j<=nLength2;j++){if(sz1[i]==sz2[j])aMaxLen[i][j]=aMaxLen[i-1][j-1]+1;else{intnLen1=aMaxLen[i][j-1];intnLen2=aMaxLen[i-1][j];if(nLen1>nLen2)aMaxLen[i][j]=nLen1;elseaMaxLen[i][j]=nLen2;}}}printf("%d\n",aMaxLen[nLength1][nLength2]);}return0;}陪審團的人選1、問題描述在遙遠的國家佛羅布尼亞，嫌犯是否有罪，須由陪審團決定。陪審團是由法官從公眾中挑選的。先隨機挑選n個人作為陪審團的候選人，然后再從這n個人中選m人組成陪審團。選m人的辦法是：控方和辯方會根據(jù)對候選人的喜歡程度，給所有候選人打分，分值從0到20。為了公平起見，法官選出陪審團的原則是：選出的m個人，必須滿足辯方總分和控方總分的差的絕對值最小。如果有多種選擇方案的辯方總分和控方總分的之差的絕對值相同，那么選辯控雙方總分之和最大的方案即可。最終選出的方案稱為陪審團方案。問題描述輸入數(shù)據(jù)輸入包含多組數(shù)據(jù)。每組數(shù)據(jù)的第一行是兩個整數(shù)n和m，n是候選人數(shù)目，m是陪審團人數(shù)。注意，1<=n<=200,1<=m<=20而且m<=n。接下來的n行，每行表示一個候選人的信息，它包含2個整數(shù)，先后是控方和辯方對該候選人的打分。候選人按出現(xiàn)的先后從1開始編號。兩組有效數(shù)據(jù)之間以空行分隔。最后一組數(shù)據(jù)n=m=0輸出要求對每組數(shù)據(jù)，先輸出一行，表示答案所屬的組號,如'Jury#1','Jury#2',等。接下來的一行要象例子那樣輸出陪審團的控方總分和辯方總分。再下來一行要以升序輸出陪審團里每個成員的編號，兩個成員編號之間用空格分隔。每組輸出數(shù)據(jù)須以一個空行結(jié)束。問題描述輸入樣例421223416200輸出樣例Jury#1Bestjuryhasvalue6forprosecutionandvalue4fordefence:232、解題思路為敘述方便，將任一選擇方案中，辯方總分和控方總分之差簡稱為“辯控差”，辯方總分和控方總分之和稱為“辯控和”。第i個候選人的辯方總分和控方總分之差記為V(i)，辯方總分和控方總分之和記為S(i)?，F(xiàn)用f(j,k)表示，取j個候選人，使其辯控差為k的所有方案中，辯控和最大的那個方案（該方案稱為“方案f(j,k)”）的辯控和。并且，我們還規(guī)定，如果沒法選j個人，使其辯控差為k，那么f(j,k)的值就為-1，也稱方案f(j,k)不可行。本題是要求選出m個人，那么，如果對k的所有可能的取值，求出了所有的f(m,k)(-20×m≤k≤20×m)，那么陪審團方案自然就很容易找到了。2、解題思路問題的關(guān)鍵是建立遞推關(guān)系。顯然，方案f(j,k)是由某個可行的方案f(j-1,x)(-20×m≤x≤20×m)演化而來的。可行方案f(j-1,x)能演化成方案f(j,k)的必要條件是：存在某個候選人i，i在方案f(j-1,x)中沒有被選上，且x+V(i)=k。在所有滿足該必要條件的f(j-1,x)中，選出

f(j-1,x)+S(i)的值最大的那個，那么方案f(j-1,x)再加上候選人i，就演變成了方案

f(j,k)。由上面知一個方案都選了哪些人需要全部記錄下來。不妨將方案f(j,k)中最后選的那個候選人的編號，記在二維數(shù)組的元素path[j][k]中。那么方案f(j,k)的倒數(shù)第二個人選的編號，就是path[j-1][k-V[path[j][k]]]。假定最后算出了方案的辯控差是k，那么從path[m][k]出發(fā)，就能順藤摸瓜一步步求出所有被選中的候選人。2、解題思路初始條件，只能確定f(0,0)=0。由此出發(fā)，一步步自底向上遞推，就能求出所有的可行方案f(m,k)(-20×m≤k≤20×m)。實際解題的時候，會用一個二維數(shù)組f來存放f(j,k)的值。而且，由于題目中辯控差的值k可以為負數(shù)，而程序中數(shù)租下標不能為負數(shù)，所以，在程序中不妨將辯控差的值都加上20×m，以免下標為負數(shù)導致出錯，即題目描述中，如果辯控差為0，則在程序中辯控差為20×m。3、參考程序#include<stdio.h>#include<stdlib.h>#include<memory.h>intf[30][1000];intPath[30][1000];intP[300];//控方打分intD[300];//辯方打分intAnswer[30];//存放最終方案的人選intCompareInt(constvoid*e1,constvoid*e2){return*((int*)e1)-*((int*)e2);}3、參考程序intmain(void){inti,j,k;intt1,t2;intn,m;intnMinP_D;//辯控雙方總分一樣時的辯控差intnCaseNo;//測試數(shù)據(jù)編號nCaseNo=0;scanf("%d%d",&n,&m);while(n+m){nCaseNo++;for(i=1;i<=n;i++)scanf("%d%d",&P[i],&D[i]);memset(f,-1,sizeof(f));memset(Path,0,sizeof(Path));nMinP_D=m*20;//題目中的辯控差為0//對應(yīng)到程序中辯控差就是m*20f[0][nMinP_D]=0;//選0個人辯控差為0的方案，其辯控和就是03、參考程序

for(j=0;j<m;j++){//每次循環(huán)選出第j個人，共要選