冬令營講義動態(tài)算法在信息學競賽中應(yīng)用

要了解動態(tài)規(guī)劃的概念，首先要知道多階段決策問題如果一類活動過程可以分為若干個互相聯(lián)系的階段，在每一個階段都需作出決策(采選擇，因而就有許多策略供選取，對應(yīng)于一個策略可以確定活動的效果，這個效果可讓先來看下面的例子：的是一個帶權(quán)有向的多段圖，要求從A到D的最1能盡人意。讓來試用動態(tài)規(guī)劃的思路分析這道題：從圖中可以看到，A點要到達D點B1B2ADB1D5，B2到D2。同樣的，B1到DC1D3C2到D2，……。G[i]iDG[C1]=4，G[C2]=3，G[C3]=5，根據(jù)上面的分所以A到D的最短距離是10，最短路徑是A→B1→C2→D階段：把所給求解問題的過程恰當?shù)胤指蓚€相互聯(lián)系的階段，以便于求解，過程A，AB，第三個階段B到點CCD。狀態(tài)：狀態(tài)表示每個階段開始的自然狀況或客觀條件，它不以人們的意志為面的例子中，第一個階段有一個狀態(tài)即A，而第二個階段有兩個狀態(tài)B1和B2，C1，C2C3D。狀態(tài)可以有多個分量(情)因而用向量來代表而且在每個階段的狀態(tài)維數(shù)可以不同。定了。換句話程的每一次實現(xiàn)可以用一個狀態(tài)序列表示，面的例子中每階段的給定k階段狀態(tài)變量x(k)的值后，如果這一階段的決策變量一經(jīng)確定，第k+1階段的狀態(tài)變量x(k+1)也就完全確定，即x(k+1)的值隨x(k)和第k階段的決策u(k)的值變化而變化，那么可以把這一關(guān)系看成(x(k)u(k))x(k+1)確定的對應(yīng)關(guān)系，用x(k+1)=Tk(x(k),u(k))表示。這是從k階段到k+1階段的狀態(tài)轉(zhuǎn)移規(guī)律，稱為狀態(tài)轉(zhuǎn)移方最優(yōu)性原理實際上是要求問題的最優(yōu)策略的子策略也是最優(yōu)。讓通過對前面的例子再分析來具體說明這一點：從A到D，知道，最短路徑是A→B1→C2→D，這些點A→B1→C2AC2最短路徑，B1→C2→DB1D最短路徑……──事實正是問題：HPCWinterCamp現(xiàn)在有一項時間緊迫的工程計算任務(wù)要交給你——國家高性能并行計算機的主管工程師——來完成為了盡可能充分發(fā)揮并行計算機的優(yōu)勢的計算任務(wù)應(yīng)當劃分AB兩個互不相關(guān)的較小的計算任務(wù)。為了充分發(fā)揮并行B類的子任務(wù)的工作量不一定相同。AB兩個計算任務(wù)之間，以及各子任務(wù)之間都沒cache。然而由于常年使用和不連貫的升級，各個計算節(jié)點的計算能力并不對稱。一個執(zhí)行A類任務(wù)；B類狀態(tài)下執(zhí)行B類任務(wù)；待機狀態(tài)下不執(zhí)行計算。所有的處理器在開始工作之前都處于待機狀態(tài)，而從其它的狀態(tài)轉(zhuǎn)入AB的工作狀態(tài)（包括AB之間相個正整數(shù)tiA和tiB(i=1,2,…,p)i轉(zhuǎn)入工作狀態(tài)A和工作狀態(tài)B（單位：nsixAtix個BitkBi其中，kiA和kiAns。i=1,2,…,pAB類子任務(wù)組成。兩類子任務(wù)可以交錯排列。nAnBApii+2行描述，該行包括：ttkk ttkk ， 分析，以不受影響。因此可以先考慮一個節(jié)點，即p=，1Btatb，處理連續(xù)任務(wù)所需的時間系數(shù)分別為kakb。如果要處理aA類任務(wù)，b個B類任務(wù)，可以分兩種情況：由于最后處理的是任務(wù)A，故可設(shè)最后連續(xù)處理了x個A類任務(wù)而實際上需要處理a個A類任a–x個A類任b個BB類任務(wù)。2xAA因此，在假定最后連續(xù)處理xA類任務(wù)的前提B類任務(wù)所需的最短時間+kax2+ta下面就來看看最后處理的是B類任務(wù)的情B

2A3B，了x個B類任務(wù)。而實際上需要處理a個A類任務(wù)，b個B類任務(wù)，因此，在處理這x個B任務(wù)之前須先完成一個子任務(wù)，它包括a個A類任務(wù)和b–x個B類任務(wù)，A類任務(wù)。顯然，這個子任務(wù)也必須是采用最優(yōu)的方案。，如圖4-3，最后連續(xù)處理了x個B類任務(wù)的時間是kbx2。節(jié)點轉(zhuǎn)入工作狀態(tài)B的時間是tb。因此，在假定最后連續(xù)處理xB類任務(wù)的前提下，處理aA類任務(wù)，bB類aA類任務(wù)，bx個BA類任務(wù)所需的最短時間+kbx2+tbga(a,b)aA類任務(wù)，bBA類任務(wù)所需的最短時間，gb(a,b)aA類任務(wù)，b個BB類任務(wù)所需的最短時間，根據(jù)上面的，可以得到：ga(a,b)=min(1≤x≤a){gb(a–x,b)+kax2}+tagb(a,b)=min(1≤x≤b){ga(a,b–x)+kbx2}+如果用g(a,b)表示處理aA類任務(wù)，bB類任務(wù)所需的最短時間，這個問題可以分解為最后處理任務(wù)A或最后處理任務(wù)B兩種情況（4。因此，g(a,b)=min{ga(a,b),gb(a,這樣，就完成p=1的分析4p1如果要處理a個Ab個BAjBai個任務(wù)A和bj個任務(wù)B都必須由后p1f(p,a,b)

5aA類任務(wù)，b個B類任務(wù)所需的最少時間（5。根據(jù)上面的分析，f(p,a,b)=min(0≤i≤a,0≤j≤b){max{g(i,j),f(p–1,a–i,b–p1ga,gb,g,f(p–1),f(p)5n2O(n2)。O(pn4)O(pn4)。Finp='hpc.in';Fout='hpc.out';Infinite=MaxLongintshr1;MaxN=63;MaxP=TNode=ta,tb,ka,kb:Integer;TMap=array[0..MaxN,0..MaxN]ofLongint;na,nb,p:info:array[1..MaxP]ofTNode;now,f:TMap;procedureinit;讀入}i:Integer;assign(input,Finp);reset(input);readln(na,nb,p);fori:=1topdowithinfo[i]doreadln(ta,tb,ka,kb);procedurecalc(now:Integer;max:Longint);計算單個節(jié)點}i,j,k:Integer;q,x:da,db:array[0..MaxN]ofLongint;fa,fb:TMap;forq:=1tonadoda[q]:=sqr(q)*info[now].ka+info[now].ta;forq:=1tonbdodb[q]:=sqr(q)*info[now].kb+info[now].tb;fa[0,0]:=0;fb[0,0]:=0;fori:=0tonadoforj:=0tonbifi+j<>0thenbeginx:=max;k:=1;while(k<=i)and(da[k]<x)dobeginq:=fb[i-k,j]+da[k];ifq<xthenx:=q;k:=k+1;fa[i,j]:=x:=max;k:=while(k<=j)and(db[k]<x)dobeginq:=fa[i,j-k]+db[k];ifq<xthenx:=q;k:=k+1;fb[i,j]:=iffa[i,j]<fb[i,j]thenf[i,j]:=fa[i,elsef[i,j]:=fb[i,proceduremain;動態(tài)規(guī)劃}k,i,j,a,b:Integer;x:Longint;pre:TMap;calc(1,Infinite);now:=f;fork:=2topdobeginpre:=now;calc(k,now[na,nb]);fori:=0tonadoforj:=0tonbiff[i,j]<now[na,nb]thenbeginx:=f[i,j];fora:=itonadoforb:=jtonbdoif(x<now[a,b])and(pre[a-i,b-j]<now[a,b])ifx<pre[a-i,b-j]thennow[a,b]:=pre[a-i,b-elsenow[a,b]:=procedureprint;輸出}assign(output,Fout);rewrite(output);wrin(now[na,nb]);在這個例子中，用ffgg的時候，也采用了動態(tài)規(guī)劃。稱之為多次動態(tài)規(guī)劃。很多題目中，動態(tài)規(guī)劃并不是單一出現(xiàn)的，但有些例子中，這種多層次的結(jié)構(gòu)并不明顯，下一節(jié)將這個問題。2.問題：交叉(WinterCamp2001練習題r，則r3匹2匹配線段。34622137aba≠b，a,b指代任何值，并非特分a[n]b[m]f(i,j) 4-對于這個狀態(tài)的求解，可以分如下幾種情況a[i]f(i1,…a[i–…b[j–沒有從b[j]出發(fā)的匹配線段。如下圖，這種情況的解即為f(i,j–1) a[i–1] b[j– 4-f(u–1,v–1)+2 a[u– b[v– 顯然，f(i,j)就是上面三種情況中的最優(yōu)值。因此，可以列出狀態(tài)轉(zhuǎn)移方程f(i,j)

f(i1,f(i,jf(u1,v1)

a[ib[v]且1vjO((nm)2)i,j,u,va[u’]b[j]u<u’i，則用b[j]a[u’]的匹配線段，代替b[j]向a[u]的匹配線段，所得到的解不會變差。因此，u的選擇是越靠后越好。同理，v的選擇也是越靠后越好。 4- fi

f(i,j)

fijfuvf

ai

ja

bbja[][],且不存在u,使得uuibjai和ju和v的值也是確定的，這些值可以預先求u和vu[i,j]v[i,j]。易知，uij(),ui a

i ai

vij(),vi

b b f(i,j)

f(i1,f(i,jf(u(i,j)1,v(i,j)1)

a[i]b[該算法需要保存f，u，v等數(shù)組，空間復雜度是O(nm)。由規(guī)劃方程可知，計算f，u，vO(nm)O(nm)。max=k,p,q,n,m:u,v,f:array[-1..max,-1..max]ofinteger;a,b:array[0..max]ofinteger;assign(input,'input.txt');reset(input);readln(n,m);fork:=1tondoread(a[k]);fork:=1tomdoread(b[k]);forp:=1tonforq:=1tomdoifa[p-1]=b[q]thenu[p,q]:=p-1elseu[p,q]:=u[p-1,ifa[p]=b[q-1]thenv[p,q]:=q-1elsev[p,q]:=v[p,q-1];forp:=1tonforq:=1tomdoifa[p]=b[q]thenk:=0elsek:=f[u[p,q]-1,v[p,q]-1]+2;iff[p-1,q]>kthenk:=f[p-1,q];iff[p,q-1]>kthenk:=f[p,q-1];f[p,q]:=k;wrin(f[n,m]);問題：Codes(IOI words（text 碼字 word）與文本（text）都是由大寫和小寫的英語字母構(gòu)成的字符序（sequence數(shù)目，比如碼字“ALL3。的序列中，說碼字“ALL”在該序列中出現(xiàn)（occur，這里的u和v可以是任意字符 （covering sequence（文本中的所有字母由左到右從1開始，該就是該字母在文本中的位置，一個c1c2c1的起始位置大于（＞）c2c2的起始位置大于（＞）c1的終止位置，就稱它們是“不的（donotoverlap。否則稱它們是“的。（solution（item所有項目中的覆蓋序列互相沒有每個項目中的覆蓋序列長度不超過（1≤N≤100，N10011000000。WCC的任何前綴（prefix）WCW的“右側(cè)最小“覆蓋序列。例如，對于碼字“ALLtext.inp則記錄了文本。words.inpN.N組成的序列，字母之間沒有空格，根據(jù)其在文件words.inp中出現(xiàn)的次序，對所字從整數(shù)1到N進行。file“text，codes.outtext文件。（iteme，其中I是碼字的，s和e分別是該碼字所對應(yīng)的覆蓋序列的首尾位置，除首行外，分析約束條件(見原題)的項構(gòu)成。因此，求出結(jié)果之前，應(yīng)該先找到所有的項?？梢韵葘o定一個字碼，以及它的一個覆蓋序列c，若c的任何連續(xù)子序列p都不是w的覆蓋設(shè)項iw和覆蓋序列c所構(gòu)成，如果cw的最簡覆蓋序列，顯然可以找到c的一個子序列p為w的最簡覆蓋序列。因此，若結(jié)果含有非最簡項i，可以將i用對最簡項構(gòu)成。這樣，只要從文本中找到所有最簡項即可。 :array[1..10000]ofTItem; 由于文本可能達到1M，最好只讀一遍文件便求出Items。下面先定義一些變量：Len[i]i個字碼的長度。Words[i,1]Words[jijMatch[i,j]為-∞。例如，若Words[1]=’abcd，當前所讀到的文本是’aubcavbc’，因為子串’abc’(15Match[1,3]=5。如果當前讀到了文本的第Index個字符Ch，而第i個字碼的第j個字符也是Ch，則有3種情況：若j>1，則若Index-Match[i,j-1]+1≤1000(項中的覆蓋序列長度不超過1000)，由于Match[i,j]:=Match[i,j-1]Match[i,j-1]:=-∞；若j=Len[i]且Index-Match[i,j]+11000。同時，令100*10010000。數(shù)組ChsTChar :Byte;{該字符所在字碼和在該字碼中的位置 :array[1..10000]of為了便于檢索，Chs以關(guān)鍵字Ch按照字典順序排序。由于在第二種情況中，Match[i,j]Match[i,j-1]Chj按照降序排Start[x]ChsCh值為xx在字碼集合中ChsStart[x]Start[Succ(x)]-1Words.inpChsStartIndex:=0;{文件位置指針初始化}Match[1..100,1..100]:=-∞Match數(shù)組初始化}WhilenotEolndobegin{文件沒有結(jié)束}Forp:=Start[Ch]toStart[Succ(Ch)]-1do{ChsChx的元素}ifChs[p].j=1then{初始}ifIndex-Match[Chs[p].i,Chs[p].j-1]+1≤1000then{遞推}if(Chs[p].j=Len)andMatch[Chs[p].i,Chs[p].j])>0)then找到一個項}AddItem(NewItem);{NewItemItems數(shù)組末尾該算法結(jié)束后，Items中保存了所有的項，且項根據(jù)對應(yīng)的覆蓋序列的尾位置按照非通過建圖來進一步抽象該問題根據(jù)求出的Items和立有向帶權(quán)圖G=(V,E)：頂點V={V0,V1,…,Vm,Vm+1}，其中V1,V2,…,Vmi個項。V0Vm+1分別是源點和匯點，Items[0].ed:=0;Items[m+1].st:=∞。Items[i].ed<Items[j].stVjViVj有弧，則必有i<j。若不然i≥jViVj有弧，則由圖G的定義，有Items[i].ed<Items[j].stItemsedi≥j，因此Items[i].ed≥Items[j].ed≥Items[j].st，這與Items[i].ed<Items[j].st。根據(jù)這個結(jié)論，易證圖G是有向無環(huán)圖。而結(jié)果可以看作是一條V0到Vm+1的最長路F[i]V0Vi的最長路徑的長度。很容易得出狀態(tài)轉(zhuǎn)移方程：F[i]:=Max{F[j]}+Len[Items[i].Which]（0≤j≤i-1VjVi有?。〧[0]:=0O(m2)m10000，將會超時。因此，必須對上述算的m=6，Items的I012345670123648∞0456788∞G4-6(這里略去了弧的長度注意到圖G中有一個特殊的性質(zhì)：若i<jVjVk有弧ViVk有弧。例如上圖中，V4V6V0,V1,V2,V3V6都有弧。6相對應(yīng)的圖證明：由于Vj到Vk有弧，根據(jù)圖G的定義，有Items[j].ed<Items[k].st。又i<j，所以Items[i].ed≤Items[j].ed，因此Items[i].ed<Items[j].ed<Items[k].st，這就說明Vi到Vk有弧。設(shè)Vi是到Vk有弧且i最大的頂點(如上圖中，V2是到V4有弧且最大的頂點)。由上面的可知，所有不大于i的頂點到Vk都有弧。因此，有F[k]=Max(0≤p≤i){F[p]}+Len[Items[i].Which]。令Q[i]=Max(0≤p≤i){F[p]}，代入F的遞推關(guān)系式，得F[k]=Q[i]+Len[Items[k].Which]Q[i]Q[i]=Max{Q[i-1],F[i]}將F的遞推關(guān)系式代入Q的遞推關(guān)系式，可以得到新的動態(tài)規(guī)劃方程設(shè)Q[k]表示V0到Vp(0≤p≤k)最長路徑長度的最大值，Vi是到Vk有弧且i最大，i，在一般情況下，ik的值十分接近，因此算法的效率要比一般動，Items[0].Ed:=0;{S}fork:=1toMdoi:=k-1;whileItems[k].St<=Items[i].EddoDec(i);{i}ifQ[k-1]>Q[k]thenbeginIOI96Prefix有些類似，都是大量數(shù)據(jù)的統(tǒng)計問題。處另外是基于圖G與一般有向無環(huán)圖在結(jié)構(gòu)上的特殊性質(zhì)優(yōu)化生成結(jié)果的算法，programIOI99_Codes; =1000;{項中覆蓋序列的長度不超過1000} =52;{52個英文字母(包括大小寫)} =record{項類型 :Byte;{字碼 =record{字符類型 :Byte;{字符所在字碼的} :array[0..MaxItems]ofPItem;{保存找到的所有項} :array[Char]ofInteger;{521..52建 :Integer;{字符總數(shù) :array[1..MaxWords]ofInteger;{Len[i]表示第i個字碼的長度} :array[1..MaxChar+1]ofInteger;{索引表} :array[1..MaxChar]ofInteger; fori:=1toNdobeginforj:=1toLen[i]doifCharToInt[Ch]=0thenbegin{建立字符與數(shù)字的對應(yīng)關(guān)系}fori:=2toNChar+1doStart[i]:=Start[i-1]+Count[i-1];{Start數(shù)組}fori:=1toNChardoCount[i]:=Start[i]-1;fori:=1toNdo{計算Chs數(shù)組}forj:=Len[i]downto1dobegin :array[1..BufSize]ofChar;{文件緩沖} :Integer;{循環(huán)變量 :Char;{當前所讀到的字符 fori:=1toMaxWordsdobegin{初始化}forp:=1toMaxWordLendoMatch[i,p]:=-MaxItemLenBlockRead(f,Buf,BufSize,p);{BlockRead加快文件處理的速度}ifpos=BufSizethenbeginifCh=#13thenBreak;{讀到換行符，退出處理}ifp=0thenContinue;{字碼中沒有出現(xiàn)這個字符}fori:=Start[p]toStart[p+1]-1do{Match數(shù)組的更新}withChs[i]ifIndex-Match[Which,Pos-1]<MaxItemLenthenbeginifPos>1thenbeginendelseMatch[Which,1]:=Index;ifPos=Len[Which]thenbegin{產(chǎn)生一個項}untilFalse;procedurePrint;{動態(tài)規(guī)劃并輸出} :array[0..MaxItems]of :array[0..MaxItems]of fori:=1toMdobegin{規(guī)劃}whileStart<=Items[k]^.EddoDec(k);ifF[i-1]>F[i]thenbeginwhilei<>0withItems[i]^dobeginWrin(Which,'',St,'',Ed);求第k問題：的蜜月(CTSC蜜月房。賓館經(jīng)理不僅大幅度降低了蜜月房的價位，而且還對不同的顧客制定了不同的價位，以吸引不同、不同消費水平的游客。比如對于來訂蜜月房的國內(nèi)、海外個必要的信息：到達日期、離去日期和顧客。了。 的預訂單，必然會被接受，因為這對賓館和 部分，以保證賓館有秩序地運轉(zhuǎn)。顯然，對于同一時間內(nèi)發(fā)生的預定要求，賓館經(jīng)理以避免顧客間發(fā)生爭執(zhí)。經(jīng)理在做出決策后，需要將整個計劃于眾，以示公平。這是現(xiàn)在請你幫助賓館經(jīng)理，從一大堆預訂要求中，在上述原則下尋找到獲利第k大的方案。i大的方案而不區(qū)分看待。例如，假3種方案的收入同時為3，有2種方案的收入為2，則收入32的方案都屬于獲利第二大。依次類推。12輸入文件的第一行是兩個數(shù)，k（1<=k<=100）t(1<=t<=100)。其中k表示需要選擇獲利第k大的方案；t表示顧客的共劃分為t類。第三行是一個數(shù)r(0<=r<=20000)，表示共有r個預訂要求。r行每行是一個預訂要求，格式為：m1/d1TOm2/d2（1<=id<=t識預訂顧客的。最后t行每行為一個整數(shù)Pi(1<=i<=t，1<=Pi<=32767)，表示蜜月房對于代號為的顧客的日標準例：某對顧客于6月1日到達，6月3日離去，對他們的日標準為m元/天，則他2m元。k大的方案不存在，則輸出-1。分k這道題目要求第k優(yōu)值，下面就先來分析k=1的情況k1時，實際上就是要求最優(yōu)值。從問題抽象后的模型來看，k=1的情形十分類IOI99Codes。從問題的本質(zhì)上來說，這兩道題目完全相同：它們都是要求一個集線段權(quán)值和最大。從問題的規(guī)模上來看，兩道題目略有不同：Codes10000100000020000，線段端點最多在366以內(nèi)。Codes采用的是動態(tài)規(guī)劃，這道題目當然也可以同樣的方法解決。在Codes中，Codes20000 7的端點取值范圍卻遠遠小于Codes，只有366，因此可以按線段的端點來劃分階段。段的集合F[i]的值或者不選Ai中的任意一條線段F[i]=F[i-1]，或者選擇Ai中的選擇線段x，且x的左端點為s，權(quán)值為v。顯然，當F[i]最優(yōu)時，前s天的收益也必然達F[i]=F[s]+v。這樣，就得到了狀態(tài)轉(zhuǎn)移方程F[i]=max{F[i–1],max{F[x.s]+x∈Ai，x.s表示線段的左端點，x.v必然是前k大的。因此，k≠1的情況和k=1的情況可以類似的處理：如果要求最的結(jié)果為第k大，只需在每一個階段中都保留前k大的結(jié)果就可以了。即用F[i,j]i天可以達到的第j大收益。在計算F[i]的過程中，每次處理一條屬于Ai的線段x時，可以建立一個臨時數(shù)組Tmp，其中Tmp[p]表示如果選擇待處理的線段x，前i天可以達到的第p大的效益，顯然有Tmp[p]=F[x.s,p]+x.v(1≤p≤K)。再將Tmp與F[i-1]歸并取前k大即可。下面分析算法的復雜度。空間上，F(xiàn)367*20000*8156K144156300K。完全時間上，雖然是按天來劃分階段，但實際上對每條線段都處理了一次，而對于每Tmp數(shù)組和歸并排序的過程，這兩個算法的時間復雜k20000*100=200萬。也是可以承受的。{$M =array[1..MaxN]of :array[1..MaxDays]of :array[0..MaxDays]of :array[0..MaxDays]of functionGet(varStr:TStr):Integer;分解串} withStrdowhile(x[st]='')or(x[st]='/') while(x[st]<>'')and(x[st]<>'/')dobeginprocedureGetInfo;讀入} :array[1..12]of :array[1..12,1..31]of :array[1..16384]of if(xmod4=0)and(xmod100<>0)or(xmod400=0)thenDays[2]:=29;form:=1to12ford:=1toDays[m]dobeginfori:=1toxdobeginfori:=1tondoReadln(Cost[i]);procedureMain;動態(tài)規(guī)劃} fori:=0toMaxDaysdobeginfori:=1toMaxDaysdobeginwhilep<>nildobeginwhile(q<k)and(la<=Count[p^.x])and(lb<=Count[i])dobeginifa>bthenbeginendelsebeginifa=bthenInc(la)while(q<k)and(la<=Count[p^.x])dobeginwhile(q<k)and(lb<=Count[i])doprocedurePrint;輸出}ifCount[MaxDays]>=kthenWrin(F[MaxDays]^[k])elseWrin(-1);動態(tài)規(guī)劃和搜索有著千絲萬縷的關(guān)系，先來看一個例子“條形碼”是一種由亮條（lightbar）和暗條（darkbar）交替出現(xiàn)，且以暗條起頭的（bar）一般情況下，BC(n,k,m)是一個包含所有由：kn個單位，每m個單位的性質(zhì)的“條形碼”組成的集合。nk（1<=n,k,m<=30（s<=100sBC(n,k,m)BC(n.k,m)s行中每一行為輸入文件中對應(yīng)“條形碼”的。7454340分題目有兩問。容易看出，計數(shù)是求序號的基礎(chǔ)，因此先解決計數(shù)問題。原題只給了一個實例，即條形碼。為了能用計算機解決該問題，須先建立一個能夠很好描述≤xi≤m，∑(i=1..k)xi=n。相應(yīng)地，任意一個滿足上述條件的k元組唯一表示一個滿足kk∑(i=1..k)xi=n，1≤xi≤m最容易想到的是搜索算法1：由于xi的取值范圍已經(jīng)確定，可以窮舉所有的ximkm，k30，因此該算法是很低效的。數(shù)解的個數(shù)。若x1=1，則方程化為x2+x3=4-x1=4-1=3，若x1=2方程化為x2+x3=2。原方程的整數(shù)解的個數(shù)，正是方程x2+x3=3，x2+x3=2的整數(shù)解的個數(shù)的和。這樣，把含32個未知數(shù)的方程的整數(shù)解個數(shù)的問x=n，1≤x≤m1≤n≤m10個解。FuncCount(k,n):LongInt;{∑(i=1..k)xi=n，1≤xi≤m的整數(shù)解個數(shù)}ifk=1thenif1≤n≤mthenelseelsefori:=1tomnc(Count,Count(k-1,n-該程序的時間復雜度仍然為mk，但可以通過改進{***}句而將復雜度降低到O(N)，其中N為Count函數(shù)的返回值，即方程的整數(shù)解個數(shù)。具體方法是通過修改循環(huán)語句的起始值和終止值：fori:=MinItoMaxIdoInc(Count,Count(k-1,n-i));其中，MinI=Max{1,n-m*(k-1)}，in{m,n-k+1}6*108甚至方程的整數(shù)解個數(shù)的模型進一步抽象為：k個在1..m之間的數(shù)的和為n的方案為k個數(shù)。但事實上，這個并不大的變化可以很大程度上的優(yōu)化程序：用F(k,n)表示k1..mn的方案數(shù)，顯然有方程式i≠0F(0,i)=0，F(xiàn)(0,0)=1。ProcFillChar(F,Sizeof(F),0);F[0,0]:=1;fori:=1tondoforj:=1tokdoforp:=1tomifi>=pthenInc(F[i,j],F[i-p,j-ij條的條形碼的個數(shù)(1≤i≤k，1≤j≤n)。而這些信息可以很方便的解決本題的要計算一個條形碼的，可以先統(tǒng)計在字典順序中比該條形碼小的條形碼的個數(shù)。FuncIndex(n,k,p:Integer):LongInt;ifk<=1thenIndex:=1elsebeginifOdd(p)thenbeginq:=1;Delta:=1endelsebeginq:=m;Delta:=-1end;whilel[p]<>qdobeginifn>=qthenInc(x,F[n-q,k-1]);Inc(q,Delta)Inc(x,Index(n-q,k-1,Index:=xLk1001110對應(yīng)的FuncCount(k,n):LongInt;{∑(i=1..k)xi=n，1≤xi≤m的整數(shù)解個數(shù)}ifF[k,n]=NULLifk=0thenelsefori:=Max{1,n-m*(k-1)}toMin{m,n-k+1}doInc(