計(jì)算機(jī)算法設(shè)計(jì)與分析第八章 回溯法

第八章回溯法8.1一般方法8.28-皇后問(wèn)題8.3子集和數(shù)問(wèn)題18.1一般方法什么是回溯回溯回溯入口出口回溯迷宮游戲什么是回溯法回溯法是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法回溯法是以深度優(yōu)先的方式系統(tǒng)地搜索問(wèn)題的解,它適用于解一些組合數(shù)較大的問(wèn)題?；厮?問(wèn)題的解可以用一個(gè)n元組(x1,…,xn)來(lái)表示，其中的xi取自于某個(gè)有窮集Si

,并且這些解必須使得某一限界函數(shù)P(x1,…,xn)取極值。不斷地用修改過(guò)的限界函數(shù)Pi(x1,…,xn)去測(cè)試正在構(gòu)造的n元組的部分向量,看是否可能導(dǎo)致最優(yōu)解,如果不能,就將可能要測(cè)試的mi+1…mn個(gè)向量略去?；厮莘ǖ慕庑枰獫M足一組綜合的約束條件,通常分為:顯式約束和隱式約束顯式約束條件:

限定每個(gè)x只從一個(gè)給定的集合上取值,滿足顯式約束的所有元組確定一個(gè)可能的解空間例:xi>=0,si={所有非負(fù)實(shí)數(shù)}隱式約束條件:

描述了xi必須彼此相關(guān)的情況回溯法的基本概念3例:4-皇后問(wèn)題在一個(gè)4*4棋盤上放4個(gè)皇后,使每?jī)蓚€(gè)皇后之間都不能互相“攻擊”,即使得每?jī)蓚€(gè)皇后都不能在同一行、同一列及同一條斜角線上。4皇后問(wèn)題可以表示為4-元組(x1,…,x4)

，其中xi是放置皇后i所在的列號(hào)。顯式約束條件:

si={1,2,3,4},1≤i≤4隱式約束條件:

沒(méi)有兩個(gè)xi可以相同,且沒(méi)有兩個(gè)皇后可以在同一條斜角線上Q1Q2Q3Q44問(wèn)題描述:已知n+1個(gè)正數(shù):wi(1≤i≤n)和M,要求找出wi的和數(shù)是M的所有子集。

例:n=4,(w1,

w2,

w3,w4)=(11,13,24,7),M=31

滿足要求的子集是(11,13,7)和(24,7)用wi的下標(biāo)來(lái)表示解向量更為方便,因此這兩個(gè)解向量可以表示為:(1,2,4)和(3,4)顯式約束條件:xi∈{j|j是wi的下標(biāo)值,1≤j≤n}隱式約束條件:要求沒(méi)有兩個(gè)xi是相同的,且相應(yīng)的wi的和數(shù)等于M為避免產(chǎn)生同一個(gè)子集的重復(fù)情況(如(1,2,4)和(1,4,2)),附加一個(gè)隱式約束條件:xi≤xi+1,1≤j≤n例:子集和數(shù)問(wèn)題5一個(gè)問(wèn)題的解可以有多種表示形式,而這些表示形式都使得所有的解是滿足某些約束條件的多元組子集和數(shù)問(wèn)題的另一種列式表示:每一個(gè)解的子集由一個(gè)大小固定的n-元組(x1,…,xn)所表示,它使得xi∈{0,1},1≤i≤n;

如果選擇wi,則xi=1;否則xi=0解向量(1,2,4)和(3,4)可表示為(1,1,0,1)和(0,0,1,1)例:子集和數(shù)問(wèn)題6145674334101112942421415161732322021222343432526272841143031323331133813341924291342183450342………4-皇后問(wèn)題的解空間樹(shù)x1=1x2=2712345678910111213141516x2=2x2=3x2=4x2=3x2=4x2=4x1=1x1=2x1=3x1=4x3=3x3=4x3=4x3=4x4=4子集和數(shù)問(wèn)題的解空間樹(shù)1

解空間樹(shù)中的路徑對(duì)應(yīng)一個(gè)向量根結(jié)點(diǎn)到自身的空路徑對(duì)應(yīng)一個(gè)空向量()

樹(shù)中紅色的路徑分別對(duì)應(yīng)向量:(4)(1,2,4)(2,3,4)817123456789101112131415161820232425192122262728293031x1=1x1=0x2=1x3=1101010x2=0x3=0x3=1x3=0x2=1x2=0x3=1x3=0x3=1x3=01010101010子集和數(shù)問(wèn)題的解空間樹(shù)2注:結(jié)點(diǎn)按D-檢索方式編號(hào)從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的一條路徑確定解空間中的一個(gè)元組樹(shù)中紅色路徑表示元組(1,1,0,1)9解空間樹(shù)(狀態(tài)空間樹(shù))的術(shù)語(yǔ)問(wèn)題狀態(tài)(problemstate):樹(shù)中的每一個(gè)結(jié)點(diǎn)確定所求解問(wèn)題的一個(gè)問(wèn)題狀態(tài)狀態(tài)空間(statespace):由根結(jié)點(diǎn)到其他結(jié)點(diǎn)的所有路徑確定了這個(gè)問(wèn)題的狀態(tài)空間解狀態(tài)(solutionstates):是這樣一些問(wèn)題狀態(tài)S,對(duì)于這些問(wèn)題狀態(tài),由根到S的那條路徑確定了這個(gè)解空間中的一個(gè)元組答案狀態(tài)(answerstates):是這樣的一些解狀態(tài)S,對(duì)于這些解狀態(tài)而言,由根到S的這條路徑確定了這問(wèn)題的一個(gè)解10靜態(tài)樹(shù)(statictrees):樹(shù)結(jié)構(gòu)與所要解決問(wèn)題的實(shí)例無(wú)關(guān)動(dòng)態(tài)樹(shù)(dynamictrees):樹(shù)結(jié)構(gòu)是與實(shí)例相關(guān)的,且樹(shù)結(jié)構(gòu)是動(dòng)態(tài)確定的活結(jié)點(diǎn):自己已經(jīng)生成而其所有的兒子結(jié)點(diǎn)還沒(méi)有全部生成的結(jié)點(diǎn)E-結(jié)點(diǎn)(正在擴(kuò)展的結(jié)點(diǎn)):當(dāng)前正在生成其兒子結(jié)點(diǎn)的活結(jié)點(diǎn)死結(jié)點(diǎn):不再進(jìn)一步擴(kuò)展或者其兒子結(jié)點(diǎn)已全部生成的生成結(jié)點(diǎn)解空間樹(shù)(狀態(tài)空間樹(shù))的術(shù)語(yǔ)11問(wèn)題狀態(tài)的生成第一種狀態(tài)生成方法:當(dāng)前的E-結(jié)點(diǎn)R一旦生成一個(gè)新的兒子結(jié)點(diǎn)C,這個(gè)C結(jié)點(diǎn)就變成一個(gè)新的E-結(jié)點(diǎn),當(dāng)檢測(cè)完了子樹(shù)C后,R結(jié)點(diǎn)就再次成為E-結(jié)點(diǎn),生成下一個(gè)兒子結(jié)點(diǎn)。(該方法也稱為深度優(yōu)先結(jié)點(diǎn)生成法)第二種狀態(tài)生成方法:一個(gè)E-結(jié)點(diǎn)一直保持到變成死結(jié)點(diǎn)為止。它又分為兩種方法:寬度優(yōu)先生成方法(隊(duì)列方法)和D-檢索方法(棧方法)第一種狀態(tài)生成方法對(duì)應(yīng)回溯法第二種狀態(tài)生成方法對(duì)應(yīng)分枝-限界法12結(jié)點(diǎn)2變成E-結(jié)點(diǎn),它再生成結(jié)點(diǎn)3,路徑變?yōu)?1,2),即皇后1在第1列上,皇后2在第2列上,所以結(jié)點(diǎn)3被殺死,此時(shí)應(yīng)回溯13x2=22x1=1開(kāi)始把根結(jié)點(diǎn)作為唯一的活結(jié)點(diǎn),根結(jié)點(diǎn)就成為E-結(jié)點(diǎn)而且路徑為();接著生成兒子結(jié)點(diǎn),假定按自然數(shù)遞增的次序來(lái)生成兒子,那么結(jié)點(diǎn)2被生成,這條路徑為(1),即把皇后1放在第1列上kill112例:4-皇后問(wèn)題138x2=3回溯到結(jié)點(diǎn)2生成結(jié)點(diǎn)8,路徑變?yōu)?1,3),則結(jié)點(diǎn)8成為E-結(jié)點(diǎn),它生成結(jié)點(diǎn)9和結(jié)點(diǎn)11都會(huì)被殺死(即它的兒子表示不可能導(dǎo)致答案的棋盤格局),所以結(jié)點(diǎn)8也被殺死,應(yīng)回溯13x2=22x1=1kill11x3=49x3=2112123killkill例:4-皇后問(wèn)題1231413x2=415x4=3回溯到結(jié)點(diǎn)2生成結(jié)點(diǎn)13,路徑變?yōu)?1,4),結(jié)點(diǎn)13成為E-結(jié)點(diǎn),由于它的兒子表示的是一些不可能導(dǎo)致答案結(jié)點(diǎn)的棋盤格局,因此結(jié)點(diǎn)13也被殺死,應(yīng)回溯8x2=313x2=22x1=1kill11x3=49x3=2killkill14x3=2kill112123412316x3=3kill例:4-皇后問(wèn)題1518x1=213x2=415x4=313x2=22x1=1kill11x3=49x3=2killkill8x2=314x3=2kill16x3=3kill結(jié)點(diǎn)2的所有兒子表示的都是不可能導(dǎo)致答案的棋盤格局,因此結(jié)點(diǎn)2也被殺死;再回溯到結(jié)點(diǎn)1生成結(jié)點(diǎn)18,路徑變?yōu)?2)19x2=124x2=3killkill結(jié)點(diǎn)18的兒子結(jié)點(diǎn)19、結(jié)點(diǎn)24被殺死,應(yīng)回溯例:4-皇后問(wèn)題1121216131x4=3結(jié)點(diǎn)18生成結(jié)點(diǎn)29,結(jié)點(diǎn)29成為E-結(jié)點(diǎn),路徑變?yōu)?2,4);18x1=213x2=415x4=313x2=22x1=1kill11x3=49x3=2killkill8x2=314x3=2kill16x3=3kill19x2=124x2=3killkill121231234結(jié)點(diǎn)29生成結(jié)點(diǎn)30,路徑變?yōu)?2,4,1)結(jié)點(diǎn)30生成結(jié)點(diǎn)31,路徑變?yōu)?2,4,1,3),找到一個(gè)4-皇后問(wèn)題的可行解29x2=430x3=1可行解17從根結(jié)點(diǎn)出發(fā),以深度優(yōu)先方式搜索整個(gè)解空間。首先根結(jié)點(diǎn)成為一個(gè)活結(jié)點(diǎn),同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前擴(kuò)展結(jié)點(diǎn)處,搜索向縱深方向移至一個(gè)新結(jié)點(diǎn),該新結(jié)點(diǎn)成為一個(gè)新的活結(jié)點(diǎn),并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向移動(dòng),則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)應(yīng)回溯至最近的一個(gè)活結(jié)點(diǎn)處,并使該活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘ㄒ赃@種方式遞歸地在解空間中搜索,直至找到所要求的解或解空間中已沒(méi)有活結(jié)點(diǎn)時(shí)為止?；厮莘ㄋ阉鬟^(guò)程18回溯算法的形式化描述假設(shè)回溯法要找出所有的答案結(jié)點(diǎn)設(shè)(x1,x2,…,xi-1)是狀態(tài)空間樹(shù)中由根到一個(gè)結(jié)點(diǎn)的路徑，而T(x1,…xi-1)是下述所有結(jié)點(diǎn)xi的集合，它使得對(duì)于每一個(gè)xi，(x1,x2,…,xi)是一條由根到結(jié)點(diǎn)xi的路徑；假定存在一些限界函數(shù)Bi,如果路徑(x1,x2,…,xi)不可能延伸到一個(gè)答案結(jié)點(diǎn),則Bi(x1,x2,…,xi)取假值,否則取真值。解向量X(1:n)中的第i個(gè)分量,就是那些選自集合T(x1,x2,…,xi-1)且使Bi為真的xi19回溯算法的形式化描述procedureBACKTRACK(n)intk,n;localX(1:n);k=1;while(k>0)do{if(還剩有沒(méi)檢驗(yàn)的X(k)使得X(k)∈T(X(1)…X(k-1))andB(X(1)…X(k))==TRUE)then

{if(X(1)…X(k))是一條抵達(dá)答案結(jié)點(diǎn)的路徑)thenprint(X(1)…X(k));k=k+1;}elsek=k-1;}endBACKTRACK//回溯//打印數(shù)組X//考慮下一個(gè)集合在X(1)…X(k-1)已經(jīng)被選定的情況下,T(X(1)…X(k-1))給出X(k)的所有可能的取值,限界函數(shù)B(X(1)…X(k))判斷哪些X(k)滿足隱式約束條件20procedureRBACKTRACK(k)globalX(1:n);intk,n;for(滿足下式的每個(gè)X(k),X(k)∈T(X(1)…X(k-1))andB(X(1),…B(k))==true)do{if(X(1),…,X(k))是一條抵達(dá)答案結(jié)點(diǎn)的路徑

thenprint(X(1)…X(k));

callRBACKTRACK(k+1);

}endRBACKTRACK回溯算法的遞歸描述進(jìn)入算法時(shí),解向量X中的前k-1個(gè)分量X(1)…X(k-1)已經(jīng)被賦值對(duì)于所有可以由根結(jié)點(diǎn)到達(dá),并可能使限界函數(shù)B為真的結(jié)點(diǎn)X(k),判斷(X(1)…X(k))是否是一條能抵達(dá)答案結(jié)點(diǎn)的路徑21回溯法的效率估計(jì)回溯法的效率主要取決于四種因素:生成下一個(gè)X(k)的時(shí)間滿足顯式約束條件的X(k)的數(shù)目限界函數(shù)Bi的計(jì)算時(shí)間對(duì)于所有的i，滿足Bi的X(k)的數(shù)目一旦選定了一種狀態(tài)空間樹(shù)結(jié)構(gòu),前三種因素對(duì)于所要解決的實(shí)例沒(méi)有多大的關(guān)系,只有第四種因素,對(duì)于問(wèn)題的不同實(shí)例,生成的結(jié)點(diǎn)數(shù)是不相同的22回溯法的效率估計(jì)重新排列動(dòng)態(tài)狀態(tài)空間樹(shù)信息熵法蒙特卡羅方法 估計(jì)狀態(tài)空間樹(shù)展開(kāi)的節(jié)點(diǎn)數(shù)238.28-皇后問(wèn)題問(wèn)題描述:在一個(gè)8*8棋盤上放置8個(gè)皇后,使得每?jī)蓚€(gè)皇后之間都不能互相“攻擊”,即每?jī)蓚€(gè)皇后都不能在同一行、同一列及同一條斜角線上Q1Q2Q3Q4Q5Q6Q7Q88皇后問(wèn)題可以表示為8-元組(x1,…,x8),其中xi是放置皇后i所在的列號(hào)圖中的可行解表示為一個(gè)8-元組即(4,6,8,2,7,1,3,5)24a11a12a13a14a15a16a17a18a21a22a23a24a25a26a27a28a31a32a33a34a35a36a37a38a41a42a43a44a45a46a47a48a51a52a53a54a55a56a57a58a61A62a63a64a65a66a67a68a71a72a73a74a75a76a77a78a81a82a83a84a85a86a87a88用二維數(shù)組A(1:8,1:8)的下標(biāo)來(lái)標(biāo)記每個(gè)皇后的位置，那么可以看到:對(duì)于在由左到右的同一條斜角線上的每個(gè)元素具有相同的“行-列”值;對(duì)于在由右到左的同一條斜角線上的每個(gè)元素則具有相同的“行+列”值設(shè)有兩個(gè)皇后被放置在(i,j)和(k,l)位置上,那么當(dāng)且僅當(dāng)

i–j=k-l或

i+j=k+l

時(shí),它們才在同一條斜角線上。將這兩個(gè)等式分別變換成:j-l=i-k或

j-l=k-i因此當(dāng)且僅當(dāng)|j-l|=|i-k|

時(shí)(即兩個(gè)皇后所在位置的行差距等于列差距時(shí)),兩個(gè)皇后在同一條斜角線上25procedurePLACE(k)inti,k;i=1;while(i<k)do{if(X[i]==X[k]orABS(X[i]-X[k])==ABS(i-k))thenreturn(false);i=i+1;}return(true);endPLACE若一個(gè)皇后能放在第k行和第X(k)列,則返回true,否則返回falseX是全程數(shù)組,進(jìn)入此過(guò)程時(shí)已置入了k個(gè)值,ABS是絕對(duì)值函數(shù)能否放置一個(gè)新皇后的算法描述:注:兩個(gè)皇后被放置在(i,j)和(k,l)位置上所以j=X[i],l=X[k],|j-l|=|i-k|

即為ABS(X[i]-X[k])==ABS(i-k)//若兩個(gè)皇后在同一列上,或在同一對(duì)角線上,則說(shuō)明該位置不能放皇后,應(yīng)返回false值26求n-皇后問(wèn)題的回溯算法描述procedureNQUEENS(n)intk,n,X(1:n);X[1]=0;k=1;while(k>0)do{X[k]=X[k]+1;while(X[k]<=n

and

NotPLACE(k)

)do{X[k]=X[k]+1;}if(X[k]<=n)then{if(k==n)thenprint(X);else{k=k+1;X[k]=0;}}elsek=k-1;}endNQUEENS//若是一個(gè)完整的解則打印數(shù)組X//k是當(dāng)前行;X(k)是當(dāng)前列//對(duì)所有的行執(zhí)行循環(huán)語(yǔ)句//移到下一列當(dāng)該位置不能放皇后時(shí)轉(zhuǎn)到下一列//找到一個(gè)位置//否則轉(zhuǎn)到下一行//沒(méi)有合適的位置,回溯271234X001Q1PLACE(1)i=1;while(i<k)do1<1,循環(huán)不執(zhí)行return(true);X[1]=0;k=1;

while(k>0)do{X[k]=X[k]+1;while(X[k]<=nandNotPLACE(k))do1<=nandNottrue,循環(huán)不執(zhí)行if(X[k]<=n)thenif(k≠n)then不執(zhí)行

else{k=k+1=2;X[2]=0;}}endwhilek=2;

while(k>0)do{X[k]=X[k]+1;while(X[k]<=nandNotPLACE(k)

)do1<=nandNotfalse,X[k]=X[k]+1=2;2<=nandNotfalse,X[k]=X[k]+1=3;3<=nandNottrue,循環(huán)不執(zhí)行123if(X[k]<=n)thenif(k≠n)then不執(zhí)行

else{k=k+1=3;X[3]=0;}0}endwhileQ2PLACE(2)i=1;while(i<k)doif(X[i]==X[k])thenreturn(false);PLACE(2)i=1;while(i<k)doif(|X[i]-X[k]|==|i-k|)

thenreturn(false);PLACE(2)i=1;while(i<k)do{if(X[i]≠X[k]or|X[i]-X[k]|≠|(zhì)i-k|)then不執(zhí)行

i=i+1=2;結(jié)束循環(huán)}return(true);281234X130Q1Q2k=3;

while(k>0)do{X[k]=X[k]+1;while(X[k]<=nandNotPLACE(k))doif(X[k]≮n)then不執(zhí)行elsek=k-1=2;

//回溯}endwhilek=2;

while(k>0)do{X[k]=X[k]+1=3+1=4;while(X[k]<=nandNotPLACE(k)

)do1<=nandNotfalse,X[k]=X[k]+1=2;2<=nandNotfalse,X[k]=X[k]+1=3;4<=nandNottrue,循環(huán)不執(zhí)行if(X[k]<=n)thenif(k≠n)then不執(zhí)行

else{k=k+1=3;X[3]=0;}}endwhileQ213<=nandNotfalse,X[k]=X[k]+1=4;4<=nandNotfalse,X[k]=X[k]+1=5;2345405≮n,循環(huán)不執(zhí)行298.3子集和數(shù)問(wèn)題子集和數(shù)問(wèn)題:假定有n個(gè)不同的正數(shù),要求找出這些數(shù)中所有使得某和數(shù)為M的組合問(wèn)題描述:已知n+1個(gè)正數(shù):wi(1≤i≤n)和M,要求找出wi的和數(shù)是M的所有子集本節(jié)將利用大小固定的元組來(lái)研究一種回溯算法，解決這一問(wèn)題

例:n=4,(w1,

w2,

w3,w4)=(7,11,13,24),M=31

滿足要求的子集是(1,1,1,0)和(1,0,0,1)30生成圖中任一結(jié)點(diǎn)的兒子:對(duì)于i級(jí)上的一個(gè)結(jié)點(diǎn),其左兒子對(duì)應(yīng)于X(i)=1,右兒子對(duì)應(yīng)于X(i)=0對(duì)于限界函數(shù)的一種簡(jiǎn)單選擇是:當(dāng)且僅當(dāng)∑W(i)X(i)+∑W(i)≥M時(shí),

B(X(1)…X(k))=truei=1ki=k+1n若W(i)按升序排列,則限界函數(shù)可以被強(qiáng)化:1x1=1x1=02311161213101415478956x2=1x3=1101010x2=0x3=0x3=1x3=010211718251922232420x2=1x2=0x3=1x3=01010……當(dāng)且僅當(dāng)∑W(i)X(i)+∑W(i)≥Mi=1ki=k+1nB(X(1)…X(k))=true且∑W(i)X(i)+W(k+1)≤M時(shí)i=1k31procedureSUMOFSUB(s,k,r)globalfloatW(1:n);globalintX(1:n);floatr,s;intk,j;X[k]=1;if(s+W[k]==M)then {print(X[j],j=1tok);print(X[j]=0,j=k+1ton);

return;}elseif(s+W[k]+W[k+1]<=M)then

callSUMOFSUB(s+W[k],k+1,r-W[k]);if(s+r-W[k]>=Mands+W[k+1]<=M)then{X[k]=0;

callSUMOFSUB(s,k+1,r-W[k]);

}endSUMOFSUB 子集和數(shù)問(wèn)題的遞歸回溯算法//進(jìn)入此過(guò)程時(shí)X(1)…X(k)的值已確定;W(j)按非降次序排列;假定W(1)≤M,∑W(i)≥M(i=1…n);j=1j=kk-1ns=∑W(j)X(j);r=∑W(j)//生成左兒子//若找到子集,則打印//否則當(dāng)Bk=true時(shí),

遞歸生成左兒子//當(dāng)Bk=true時(shí)遞歸生成右兒子32實(shí)例:n=6,M=30,W(1:n)=(5,10,12,13,15,18)j=1j=kk-1ns=∑W(j)X(j);r=∑W(j)SUMOFSUB(s,k,r)開(kāi)始調(diào)用時(shí)k=1,由公式算出s=0,r=73(注:為書寫簡(jiǎn)便將SUMOFSUB縮寫為SB)①SB(0,1,73)//s=0,k=1,r=73X[1]=1;if(s+W[k]==M)then0+5=5≠300+5+10=15<300+5=5,1+1=2,73-5=68等待執(zhí)行的部分:if(s+r-W[k]>=Mands+W[k+1]<=M)then{X[k]=0;callSB(s,k+1,r-W[k]);}end①SB0,1,735,2,68X[1]=1不執(zhí)行elseif(s+W[k]+W[k+1]<=M)thencall②SB(s+W[k],k+1,r-W[k]);33②SB(5,2,68)//s=5,k=2,r=68X[2]=1;if(s+W[k]==M)then5+10=15≠305+10+12=27<305+10=15,2+1=3,68-10=58等待執(zhí)行的部分:if(s+r-W[k]>=Mands+W[k+1]<=M)then{X[k]=0;callSB(s,k+1,r-W[k]);}end②SB不執(zhí)行else

if(s+W[k]+W[k+1]<=M)thencall③SB(s+W[k],k+1,r-W[k]);0,1,735,2,68X[1]=115,3,58X[2]=134else

if(s+W[k]+W[k+1]<=M)then③SB(15,3,58)//s=15,k=3,r=58X[3]=1;if(s+W[k]==M)then15+12=27≠3015+12+13=40>3015+58-12=61>30and15+13=28<30不執(zhí)行不執(zhí)行if(s+r-W[k]>=Mands+W[k+1]<=M)then{X[3]=0;call④SB(s,k+1,r-W[k]);}15,3+1=4,58-12=46end③SB15,4,46X[3]=00,1,735,2,68X[1]=115,3,58X[2]=135④SB(15,4,46)//s=15,k=4,r=46X[4]=1;if(s+W[k]==M)then15+13=28≠3015+13+15=43>30不執(zhí)行else

if(s+W[k]+W[k+1]<=M)then不執(zhí)行if(s+r-W[k]>=Mands+W[k+1]<=M)then{X[4]=0;call⑤SB(s,k+1,r-W[k]);}15,4+1=5,46-13=33end④SB15+46-13=48>30and15+15=30=300,1,735,2,68X[1]=115,3,58X[2]=115,4,46X[3]=015,5,33X[4]=036⑤SB(15,3,33)//s=15,k=5,r=33X[5]=1;if(s+W[k]==M)then15+15=30==M{forj=1tokdoprint(X[j]);forj=k+1tondo

print(X[j]=0);

return;

}打印X=(1,1,0,0,1,0)end⑤S