N皇后問(wèn)題 回溯法

回溯

Backtracking回溯N皇后問(wèn)題跳馬問(wèn)題迷宮問(wèn)題圖的著色問(wèn)題0-1背包問(wèn)題裝載問(wèn)題批處理作業(yè)調(diào)度填數(shù)問(wèn)題組合輸出問(wèn)題算24點(diǎn)問(wèn)題ACM應(yīng)用學(xué)習(xí)要點(diǎn)掌握回溯的概念掌握經(jīng)典問(wèn)題的回溯解決方法掌握回溯與其它方法的異同有許多問(wèn)題，當(dāng)需要找出它的解集或者要求回答什么解是滿足某些約束條件的最佳解時(shí)，往往要使用回溯法?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問(wèn)題?；厮莘ㄔ趩?wèn)題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ɑ厮菟惴ㄊ撬兴阉魉惴ㄖ凶顬榛镜囊环N算法,是一種能避免不必要搜索的窮舉式的搜索算法，其基本思想就是窮舉搜索。算法思想：采用了一種“走不通就掉頭”的思想。搜索時(shí)往往有多分支，按某一分支為新的出發(fā)點(diǎn)，繼續(xù)向下探索，當(dāng)所有可能情況都探索過(guò)且都無(wú)法到達(dá)目標(biāo)的時(shí)候，再回退到上一個(gè)出發(fā)點(diǎn)，繼續(xù)探索另一個(gè)可能情況，這種不斷回頭尋找目標(biāo)的方法稱為“回溯法”?；厮莘ɑ厮菟惴ㄊ撬兴阉魉惴ㄖ凶顬榛镜囊环N算法,是一種能避免不必要搜索的窮舉式的搜索算法，其基本思想就是窮舉搜索?；厮莘ㄋ阉鞯姆绞街饕捎蒙疃葍?yōu)先搜索的方式回溯三要素：

1)解空間：該空包含問(wèn)題的解

2)約束條件

3)狀態(tài)樹問(wèn)題的解空間問(wèn)題的解向量：回溯法希望一個(gè)問(wèn)題的解能夠表示成一個(gè)n元式(x1,x2,…,xn)的形式。顯約束：對(duì)分量xi的取值限定。隱約束：為滿足問(wèn)題的解而對(duì)不同分量之間施加的約束。解空間：對(duì)于問(wèn)題的一個(gè)實(shí)例，解向量滿足顯式約束條件的所有多元組，構(gòu)成了該實(shí)例的一個(gè)解空間。注意：同一個(gè)問(wèn)題可以有多種表示，有些表示方法更簡(jiǎn)單，所需表示的狀態(tài)空間更?。ù鎯?chǔ)量少，搜索方法簡(jiǎn)單）。n=3時(shí)的0-1背包問(wèn)題用完全二叉樹表示的解空間生成問(wèn)題狀態(tài)的基本方法擴(kuò)展結(jié)點(diǎn):一個(gè)正在產(chǎn)生兒子的結(jié)點(diǎn)稱為擴(kuò)展結(jié)點(diǎn)活結(jié)點(diǎn):一個(gè)自身已生成但其兒子還沒(méi)有全部生成的節(jié)點(diǎn)稱做活結(jié)點(diǎn)死結(jié)點(diǎn):一個(gè)所有兒子已經(jīng)產(chǎn)生的結(jié)點(diǎn)稱做死結(jié)點(diǎn)深度優(yōu)先的問(wèn)題狀態(tài)生成法：如果對(duì)一個(gè)擴(kuò)展結(jié)點(diǎn)R，一旦產(chǎn)生了它的一個(gè)兒子C，就把C當(dāng)做新的擴(kuò)展結(jié)點(diǎn)。在完成對(duì)子樹C（以C為根的子樹）的窮盡搜索之后，將R重新變成擴(kuò)展結(jié)點(diǎn)，繼續(xù)生成R的下一個(gè)兒子（如果存在）寬度優(yōu)先的問(wèn)題狀態(tài)生成法：在一個(gè)擴(kuò)展結(jié)點(diǎn)變成死結(jié)點(diǎn)之前，它一直是擴(kuò)展結(jié)點(diǎn)回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問(wèn)題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來(lái)處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問(wèn)題的計(jì)算量。具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法回溯法的基本思想(1)針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；(2)確定易于搜索的解空間結(jié)構(gòu)；(3)以深度優(yōu)先方式搜索解空間，并在搜索過(guò)程中用剪枝函數(shù)避免無(wú)效搜索。常用剪枝函數(shù)：用約束函數(shù)在擴(kuò)展結(jié)點(diǎn)處剪去不滿足約束的子樹；用限界函數(shù)剪去得不到最優(yōu)解的子樹。用回溯法解題的一個(gè)顯著特征是在搜索過(guò)程中動(dòng)態(tài)產(chǎn)生問(wèn)題的解空間。在任何時(shí)刻，算法只保存從根結(jié)點(diǎn)到當(dāng)前擴(kuò)展結(jié)點(diǎn)的路徑。如果解空間樹中從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度為h(n)，則回溯法所需的計(jì)算空間通常為O(h(n))。而顯式地存儲(chǔ)整個(gè)解空間則需要O(2h(n))或O(h(n)!)內(nèi)存空間。遞歸回溯回溯法對(duì)解空間作深度優(yōu)先搜索，因此，在一般情況下用遞歸方法實(shí)現(xiàn)回溯法。voidbacktrack(intt){

if(t>n)output(x);

elsefor(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);if(constraint(t)&&bound(t))backtrack(t+1);}}迭代回溯采用樹的非遞歸深度優(yōu)先遍歷算法，可將回溯法表示為一個(gè)非遞歸迭代過(guò)程。voiditerativeBacktrack(){intt=1;

while(t>0){

if(f(n,t)<=g(n,t))for(inti=f(n,t);i<=g(n,t);i++){x[t]=h(i);

if(constraint(t)&&bound(t)){

if(solution(t))output(x);

elset++;}}

elset--;}}在一個(gè)n*n的國(guó)際象棋棋盤上放置n個(gè)皇后，使得它們中任意2個(gè)之間都不互相“攻擊”，即任意2個(gè)皇后不可在同行、同列、同斜線上。輸出N，⑴求N皇后問(wèn)題的一種放法；

⑵求N皇后問(wèn)題的所有放法分析：

N=4時(shí)，右圖是一組解要素一：解空間一般想法：利用二維數(shù)組，用[i,j]確定一個(gè)皇后位置！

優(yōu)化：利用約束條件，只需一維數(shù)組即可！

x:array[1..n]ofinteger;x[i]：i表示第i行皇后

x[i]表示第i行上皇后放第幾列

x[3,1,4,2]N皇后問(wèn)題要素二：約束條件不同行：數(shù)組x的下標(biāo)保證不重復(fù)不同列：x[i]<>x[j](i<=I,j<=n；i<>j)不同對(duì)角線：abs(x[i]-x[j])<>abs(i-j)要素三：狀態(tài)樹將搜索過(guò)程中的每個(gè)狀態(tài)用樹的形式表示出來(lái)！畫出狀態(tài)樹對(duì)書寫程序有很大幫助！填到第K行時(shí)，就與前1~(K-1)行都進(jìn)行比較FunctionPlace(k:integer):boolean;place:=true;forj←1tok-1doif|k-j|=|x[j]-x[k]|orx[j]=x[k]thenplace:=falseN皇后問(wèn)題K=0K=1**************回溯**********回溯***********K=3K=2K=4****出解后可以繼續(xù)剛才的做法過(guò)程：進(jìn)入新一行，該行上按順序逐個(gè)格子嘗試，直到能放為止（不沖突、不越界）算法描述：產(chǎn)生一種新放法沖突，繼續(xù)找，直到找到不沖突----不超范圍if不沖突thenk<nk+1 k=n一組解if沖突then回溯N皇后問(wèn)題回溯部份：

即狀態(tài)恢復(fù)，使其恢復(fù)到進(jìn)入該分支前的狀態(tài)，繼續(xù)新的分支

x[k]:=0;Dec(k);

程序結(jié)束條件：一組解：設(shè)標(biāo)志，找到一解后更改標(biāo)志，以標(biāo)志做為結(jié)束循環(huán)的條件所有解：k=0程序?qū)崿F(xiàn)：回溯算法可用非遞歸和遞歸兩種方法實(shí)現(xiàn)！判斷約束函數(shù)FunctionPlace(k:integer):boolean;place:=true;forj←1tok-1doif|k-j|=|x[j]-x[k]|orx[j]=x[k]thenplace:=falseN皇后問(wèn)題Nqueens()

beginx[1]←0k←1

whilek>0dobegin

x[k]←x[k]+1

whilex[k]<=nand(notplace(k))dox[k]←x[k]+1

ifx[k]<=nthenifk=nthensum←sum+1

else

begink←k+1x[k]←0

end

elsek←k-1

end

end

非遞歸寫法：

ifk=nthenprint;flag←false算法描述：產(chǎn)生一種新放法沖突，繼續(xù)找，直到找到不沖突----不超范圍if不沖突thenk<nk+1 k=n一組解if沖突then回溯Flag←trueWhileflagdoN皇后問(wèn)題proceduretry(k:byte);

vari:byte;

begin

fori:=1tondo {每層均有n種放法}

ifplace(k)then {尋找放置皇后的位置}

begin

x[k]:=i; {放置皇后)

ifk=nthenprint {８?jìng)€(gè)皇后都放置好,輸出} {若只想找一組解，halt}

elsetry(k+1); {繼續(xù)遞歸放置下一個(gè)皇后}

end;

end;遞歸寫法：分析：狀態(tài)恢復(fù)（回溯）在什么地方實(shí)現(xiàn)？N皇后問(wèn)題在n×m棋盤上有一中國(guó)象棋中的馬：馬走日字；馬只能往右走。請(qǐng)你找出一條可行路徑，使得馬可以從棋盤的左下角（1，1）走到右上角（n，m）。輸入：95輸出：(1,1)->(3,2)->(5,1)->(6,3)->(7,1)->(8,3)->(9,5)跳馬問(wèn)題分析：按題意，馬每一步可以有4種走法！搜索過(guò)程：當(dāng)馬一開(kāi)始位于左下角的時(shí)候，根據(jù)規(guī)則，它只有兩條線路可以選擇（另外兩條超出棋盤的范圍），我們無(wú)法預(yù)知該走哪條，故任意選擇一條，到達(dá)A1。AA1A2當(dāng)?shù)竭_(dá)A1點(diǎn)后，又有三條線路可以選擇，于是再任意選擇一條，到達(dá)B1。從B1再出發(fā)，又有兩條線路可以選擇，先選一條，到達(dá)C1。AA1A2B1B2B3C1C2跳馬問(wèn)題AA1A2B1B2B3C1C2D1D2D3E14.從C1出發(fā)，可以有三條路徑，選擇D1。但到了D1以后，我們無(wú)路可走且D1也不是最終目標(biāo)點(diǎn)，因此，選擇D1是錯(cuò)誤的，我們退回C1重新選擇D2。同樣D2也是錯(cuò)誤的。再回到C1選擇D3。D3只可以到E1，但E1也是錯(cuò)誤的。返回D3后，沒(méi)有其他選擇，說(shuō)明D3也是錯(cuò)誤的，再回到C1。此時(shí)C1不再有其他選擇，故C1也是錯(cuò)誤的，退回B1，選擇C2進(jìn)行嘗試。AA1A2B1B2B3C2E2BD4E1F15.從C2出發(fā)，有四條路徑可以選擇，選擇D4，從D4出發(fā)又有兩條路徑，選擇E1錯(cuò)誤，返回D4選擇E2，從E2出發(fā)有兩條路徑，先選擇F1錯(cuò)誤，返回E2選擇B，而B恰好是我們要到達(dá)的目標(biāo)點(diǎn)，至此，一條路徑查找成功。跳馬問(wèn)題①②③④從上面的分析我們可以得知：在無(wú)法確定走哪條線路的時(shí)候，任選一條線路進(jìn)行嘗試；為方便路徑表示，對(duì)馬可以走到的四個(gè)點(diǎn)（方向）都編上號(hào)；當(dāng)從某點(diǎn)出發(fā)，所有可能到達(dá)的點(diǎn)都不能到達(dá)終點(diǎn)時(shí)，說(shuō)明此點(diǎn)是一個(gè)死節(jié)點(diǎn)，必須回溯到上一個(gè)點(diǎn)，并重新選擇一條新的線路進(jìn)行嘗試。解空間:

為了描述路徑，我們最直接的方法就是記錄路徑上所有點(diǎn)的坐標(biāo)。優(yōu)化：每一個(gè)方向上兩個(gè)坐標(biāo)和原位置對(duì)應(yīng)關(guān)系若馬所處的位置為(x,y)，則其下一步可以到達(dá)的四個(gè)位置分別是(x+1,y-2)，(x+2,y-1)，(x+2,y+1)，(x+1,y+2)。增量數(shù)組：

dx=(1,2,2,1)

dy=(-2,-1,1,2)方向t，下一步的位置就是(x+dx[t],y+dy[t])。xypath:array[1..m]ofinteger;其中，path[i]：表示第i個(gè)節(jié)點(diǎn)所走的方向跳馬問(wèn)題約束條件：不越界：(x+dx[i]<=n)and(y+dy[i]>0)and(y+dy[i]<=n)

狀態(tài)樹：0①②③④⑤⑤⑤⑥④Path[1]:=3Path[2]:=2Path[3]:=3Path[4]:=234Path[5]:=14①②③④④⑤⑤⑤⑤⑥⑥⑦⑦①②③④算法描述：產(chǎn)生一種新走法越界，繼續(xù)用新走法，直到找到一種走法不越界----不超過(guò)4種走法if不越界thenk<nk+1 k=n一組解if越界then回溯跳馬問(wèn)題Horse()

beginpath[1]←0，k←1，x←1，y←1

while(x<>m)and(y<>n)dobegin

path[k]←path[k]+1

while(x+dx[i]<=n)and(y+dy[i]>0)and(y+dy[i]<=n)

and (path[k]<=4)dopath[k]←path[k]+1

ifpath[k]<=4then {在4種走法中找到不越界的走法}beginx←x+dx[i]，y←y+dy[i]if(x<>m)and(y<>n)thenprint

else

begink←k+1path[k]←0

end

end

elsepath[k]←0，k←k-1

end

end

跳馬問(wèn)題（非遞歸）跳馬問(wèn)題跳馬問(wèn)題（遞歸）跳馬問(wèn)題proceduresearch(k:integer);//遞歸查找beginfori:=1to4do//依次嘗試四個(gè)方向

if(x+dx[i]<=n)and(y+dy[i]>0)and(y+dy[i]<=n)then//在棋盤上

beginpath[k]:=i;//記錄下當(dāng)前方向

x:=x+dx[i];y:=y+dy[i];//修改擴(kuò)展節(jié)點(diǎn)坐標(biāo)

if(x=n)and(y=m)then//是否是目標(biāo)點(diǎn)

beginoutput(k);halt;//是目標(biāo)點(diǎn)，輸出結(jié)果并終止程序

endelsesearch(k+1);//不是目標(biāo)點(diǎn)，繼續(xù)嘗試下一步

//擴(kuò)展出的點(diǎn)是死點(diǎn)，回溯

x:=x-dx[i];y:=y-dy[i];//恢復(fù)擴(kuò)展節(jié)點(diǎn)坐標(biāo)，狀態(tài)恢復(fù)

end;end;Beginread(n,m);x:=1;y:=1;search(1);End.思考:1.在本例中，我們只要求輸出一條可行路徑，如果我們需要輸出所有的可行路徑，怎樣改動(dòng)此程序呢？<遞歸><非遞歸>2.如果我們把問(wèn)題改成“在n×m的棋盤上有一騎士，開(kāi)始時(shí)，騎士在點(diǎn)(x,y)，現(xiàn)在請(qǐng)你找出一條可行的路徑，使得騎士可以不重復(fù)的走遍棋盤上的每一個(gè)點(diǎn)。”的話，又要如何編寫此程序呢？跳馬問(wèn)題

設(shè)有一個(gè)N*N方格的迷宮，入口和出口分別在左上角和右上角，迷宮格子中分別放有0和1，0表示可走，1表示不能走，迷宮走的規(guī)則如圖。當(dāng)迷宮給出之后，找出一條從入口到出口的通路。輸入：NN*N的迷宮輸出：具體路徑輸入樣例：

8輸出樣例：(1,1)-(2,1)-(3,1)-(2,2)-(1,3)-(2,4)-(3,3)-(4,3)-(5,2)-(6,3)-(7,3)-(8,2)-(8,1)迷宮問(wèn)題xy①②③④⑤⑥⑦⑧分析：增量和方向表示

dx=(1,1,-1,-1,1,-1,0,0)dy=(-1,0,1,0,1,-1,1,-1)path:array[1..maxn*maxn]ofinteger;其中，path[i]：表示第i個(gè)節(jié)點(diǎn)所走的方向解空間約束條件不越界且該點(diǎn)可走(x>=1)and(x<=N)and(y>=1)and(y<=N)andA[x,y]=1迷宮信息用二維數(shù)組表示

A:array[1..maxn,1..maxn]of0..1;入口（1,1）；出口（n,1）狀態(tài)樹迷宮問(wèn)題給定無(wú)向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個(gè)頂點(diǎn)著不同顏色。這個(gè)問(wèn)題是圖的m可著色判定問(wèn)題。若一個(gè)圖最少需要m種顏色才能使圖中每條邊連接的2個(gè)頂點(diǎn)著不同顏色，則稱這個(gè)數(shù)m為該圖的色數(shù)。求一個(gè)圖的色數(shù)m的問(wèn)題稱為圖的m可著色優(yōu)化問(wèn)題。圖的著色問(wèn)題

有形如下列圖形的地圖，圖中每一塊區(qū)域代表一個(gè)省份，現(xiàn)請(qǐng)你用紅（1）、蘭（2）、黃（3）、綠（4）四種顏色給這些省份填上顏色，要求每一省份用一種顏色，且任意兩個(gè)相鄰省份的顏色不能相同，請(qǐng)給出一種符合條件的填色方案。1234567圖的存儲(chǔ)R:array[1..n,1..n]of0..1;其中，R[I,j]=0------省i和省j不相鄰

=1------省i和省j相鄰①②③④⑤⑥⑦將實(shí)際地圖用無(wú)向圖的形式給出，每個(gè)省份代表圖上的一個(gè)頂點(diǎn)，邊代表兩個(gè)省份是相鄰的。四色問(wèn)題圖的著色問(wèn)題解向量：(x1,x2,…,xn)表示頂點(diǎn)i所著顏色x[i]

可行性約束函數(shù)：頂點(diǎn)i與已著色的相鄰頂點(diǎn)顏色不重復(fù)。voidColor::Backtrack(intt){if(t>n){sum++;for(inti=1;i<=n;i++)cout<<x[i]<<'';cout<<endl;}elsefor(inti=1;i<=m;i++){x[t]=i;if(Ok(t))Backtrack(t+1);}}boolColor::Ok(intk){//檢查顏色可用性

for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))returnfalse;returntrue;}圖的著色問(wèn)題1234567算法思想：從編號(hào)1的省開(kāi)始，按4種顏色的排列順序，首先選擇第一種顏色，然后檢查是否矛盾，即相鄰的區(qū)域中是否已有該顏色，若不矛盾，則涂色，若矛盾，則選擇下一個(gè)顏色，再判斷，當(dāng)4種顏色都不可能時(shí)，則需回溯。當(dāng)?shù)谝粋€(gè)省的顏色確定之后，依次對(duì)第二個(gè)省、第三個(gè)省……進(jìn)行處理，當(dāng)所有省都涂上顏色之后，得到一種解法。color:array[1..maxn]ofinteger;其中，color[k]：表示第k個(gè)省所填的顏色解空間Color(1,2,1,3,1,3,4)迷宮問(wèn)題Functionpd(k:integer):boolean;Varm:integer;Beginm:=1;{從第一個(gè)省份開(kāi)始檢查是否沖突}pd:=true;{不沖突}

while(m<k)and(color[k]*g[m,k]<>color[m])doinc(m);ifk>=mthenpd:=false;{沖突}End;約束條件該點(diǎn)k涂的顏色(color[k)與和k相鄰的點(diǎn)m(1<=m<=k-1)的顏色(color[m])相同

color[k]*g[m,k]=color[m]狀態(tài)樹迷宮問(wèn)題proceduresearch(k:integer);{遞歸搜索第m個(gè)省份}beginifk>nthen {是否所有省份都已經(jīng)填色}beginwrite(color[1]);{已全部填色，輸出結(jié)果，終止程序}forj:=2tondowrite('',color[j]);writeln;haltendelse {還未全部填色}forj:=1to4dobegin{依次用四種顏色對(duì)當(dāng)前省份填色}if(k<=n)andpd(k)then {沒(méi)有沖突}begincolor[k]:=j; {記錄當(dāng)前省份顏色}search(k+1); {遞歸檢查下一個(gè)省份}end;end;end;四色問(wèn)題（遞歸）迷宮問(wèn)題輸入：第一行一個(gè)整數(shù)，為背包的容量M；第二行一個(gè)整數(shù)，為物品的種數(shù)Ｎ；第三行Ｎ個(gè)整數(shù)為各物品的重量；第四行Ｎ個(gè)整數(shù)分別為Ｎ個(gè)物品的價(jià)值輸出：第一行為最大總價(jià)值；第二行為裝入的各物品的重量（未裝的物品用０）；第三行為裝入的各物品的價(jià)值（未裝的物品用０）

已知一個(gè)容量大小為M重量的背包和N種物品，每種物品的重量為Wi。若將物品放入背包將得到Pi的效益，求怎樣選取物品將得到效益最大輸入樣例：

50

3

102030

60100120

輸出樣例：

220

02030

0100120測(cè)試數(shù)據(jù)：

輸入：

10

5

22654

63546

輸出：

?0-1背包問(wèn)題bag:array[1..maxn]of0..1;其中，bag[k]=1表示第k個(gè)物品要取

0表示第k個(gè)物品不取解空間約束條件第k個(gè)物品確定放置方法后，背包所剩重量足夠放第K個(gè)物品wei-bag[k]*w[k]>=0 {wei：背包還能裝的重量}Best:=0;表示最大價(jià)值當(dāng)一組解產(chǎn)生后，得到當(dāng)前總價(jià)值count，

ifcount>bestthenbest:=count利用這種方法記錄最優(yōu)解！如果還要記錄最優(yōu)時(shí)的物品取法應(yīng)：ifcount>bestthenbegin best:=count; fori:=1tondoy[i]:=bag[i];狀態(tài)樹求最優(yōu)值0-1背包問(wèn)題本題可以用遞歸求解：本題可用方法很多！非遞歸寫法與前幾題相似，請(qǐng)自己寫出！算法分析：

設(shè)當(dāng)前有N個(gè)物品，容量為M；這些物品要么選，要么不選，我們假設(shè)選的第一個(gè)物品編號(hào)為i（1~i-1號(hào)物品不選），問(wèn)題又可以轉(zhuǎn)化為有N-I個(gè)物品（即第I+1~N號(hào)物品），容量為M-Wi的子問(wèn)題……如此反復(fù)下去，然后在所有可行解中選一個(gè)效益最大的便可?；厮荩顟B(tài)恢復(fù)）后，需恢復(fù)的狀態(tài)有：Bag[k]背包可裝的物品重量：wei:=wei+w[k]*i已裝物品的價(jià)值總和：count:=count:-c[k]*i0-1背包問(wèn)題procedurework(k,wei:integer);vari,j:integer;beginfori:=1downto0doif(wei-w[k]*i>=0)thenbeginbag[k]:=i;count:=count+c[k]*i;if(k=n)and(count>best)thenbeginbest:=count;forj:=1tondoy[j]:=bag[j];end;ifk<nthenwork(k+1,wei-w[k]*i);count:=count-c[k]*i;{狀態(tài)恢復(fù)}end;end;(k)(k,wei,count)work(k+1)wei:=wei+w[k]*iwork(k+1,wei-w[k])*i,count)0-1背包（遞歸）wei:=wei-w[k]*i0-1背包問(wèn)題有一批共n個(gè)集裝箱要裝上2艘載重量分別為c1和c2的輪船，其中集裝箱i的重量為wi，且裝載問(wèn)題要求確定是否有一個(gè)合理的裝載方案可將這個(gè)集裝箱裝上這2艘輪船。如果有，找出一種裝載方案。容易證明，如果一個(gè)給定裝載問(wèn)題有解，則采用下面的策略可得到最優(yōu)裝載方案。(1)首先將第一艘輪船盡可能裝滿；(2)將剩余的集裝箱裝上第二艘輪船。將第一艘輪船盡可能裝滿等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱重量之和最接近。由此可知，裝載問(wèn)題等價(jià)于以下特殊的0-1背包問(wèn)題。用回溯法設(shè)計(jì)解裝載問(wèn)題的O(2n)計(jì)算時(shí)間算法。在某些情況下該算法優(yōu)于動(dòng)態(tài)規(guī)劃算法。裝載問(wèn)題解空間：子集樹可行性約束函數(shù)(選擇當(dāng)前元素)：上界函數(shù)(不選擇當(dāng)前元素)：當(dāng)前載重量cw+剩余集裝箱的重量r當(dāng)前最優(yōu)載重量bestwvoidbacktrack(inti){//搜索第i層結(jié)點(diǎn)

if(i>n)//到達(dá)葉結(jié)點(diǎn)更新最優(yōu)解bestx,bestw;return;r-=w[i];

if(cw+w[i]<=c){//搜索左子樹

x[i]=1;cw+=w[i];

backtrack(i+1);cw-=w[i];}

if(cw+r>bestw){x[i]=0;//搜索右子樹

backtrack(i+1);}r+=w[i];}裝載問(wèn)題給定n個(gè)作業(yè)的集合{J1,J2,…,Jn}。每個(gè)作業(yè)必須先由機(jī)器1處理，然后由機(jī)器2處理。作業(yè)Ji需要機(jī)器j的處理時(shí)間為tji。對(duì)于一個(gè)確定的作業(yè)調(diào)度，設(shè)Fji是作業(yè)i在機(jī)器j上完成處理的時(shí)間。所有作業(yè)在機(jī)器2上完成處理的時(shí)間和稱為該作業(yè)調(diào)度的完成時(shí)間和。批處理作業(yè)調(diào)度問(wèn)題要求對(duì)于給定的n個(gè)作業(yè)，制定最佳作業(yè)調(diào)度方案，使其完成時(shí)間和達(dá)到最小。這3個(gè)作業(yè)的6種可能的調(diào)度方案是1,2,3；1,3,2；2,1,3；2,3,1；3,1,2；3,2,1；它們所相應(yīng)的完成時(shí)間和分別是19，18，20，21，19，19。易見(jiàn)，最佳調(diào)度方案是1,3,2，其完成時(shí)間和為18。批處理作業(yè)問(wèn)題解空間：排列樹voidFlowshop::Backtrack(inti){if(i>n){for(intj=1;j<=n;j++)bestx[j]=x[j];bestf=f;}elsefor(intj=i;j<=n;j++){f1+=M[x[j]][1];f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if(f<bestf){Swap(x[i],x[j]);Backtrack(i+1);Swap(x[i],x[j]);}f1-=M[x[j]][1];f-=f2[i];}}classFlowshop{friendFlow(int**,int,int[]);private:voidBacktrack(inti);int**M,//各作業(yè)所需的處理時(shí)間*x,//當(dāng)前作業(yè)調(diào)度*bestx,//當(dāng)前最優(yōu)作業(yè)調(diào)度*f2,//機(jī)器2完成處理時(shí)間

f1,//機(jī)器1完成處理時(shí)間

f,//完成時(shí)間和

bestf,//當(dāng)前最優(yōu)值

n;//作業(yè)數(shù)};批處理作業(yè)問(wèn)題【問(wèn)題描述】

從整數(shù)1到10中任取9個(gè)不同的數(shù)，填入下面的9個(gè)格子中，使所有相鄰（左、右、上、下）兩個(gè)格子中的數(shù)的和是素?cái)?shù)?！据敵觥?/p>

一行3個(gè)數(shù)，共3行?！緲永?/p>

125 438 7109【說(shuō)明】

輸出所有本質(zhì)不同的解。（通過(guò)某個(gè)解的旋轉(zhuǎn)、上下翻轉(zhuǎn)、左右翻轉(zhuǎn)得到的是本質(zhì)相同的）填數(shù)問(wèn)題【問(wèn)題描述】

排列與組合是常用的數(shù)學(xué)方法，其中組合