第五章

回溯法2025/7/31用計算機求解問題問題空間現(xiàn)實求解過程實際解狀態(tài)空間對象的定義機器求解過程算法與程序的設計機內(nèi)解2025/7/32計算機求解的過程在狀態(tài)空間尋找機內(nèi)解可以看成是從初始狀態(tài)出發(fā)搜索目標狀態(tài)(解所在的狀態(tài))的過程。狀態(tài)空間初始狀態(tài)目標狀態(tài)搜索搜索的過程可描述為：S0

S1…Sn，其中S0為初態(tài)，Sn為終態(tài)?；蛘哒fψ(S0)且φ(Sn)，這里ψ稱為初始條件，φ稱為終止條件。2025/7/33求解是狀態(tài)空間的搜索求解的過程可以描述為對狀態(tài)空間的搜索S0S11S12…S1k………………Sn1……Sni……Snm其中S0為初始狀態(tài)，不妨設Sni為終止狀態(tài)S0Sni于是問題的求解就是通過搜索尋找出一條從初始狀態(tài)S0到終止狀態(tài)Sni的路徑。2025/7/34幾種搜索方法狀態(tài)空間的搜索實際上是一種樹的搜索，常用的方法有：廣度優(yōu)先的搜索深度優(yōu)先的搜索啟發(fā)式的搜索從初始狀態(tài)開始，逐層地進行搜索。從初始狀態(tài)開始，逐個分枝地進行搜索。從初始狀態(tài)開始，每次選擇最有可能到達終止狀態(tài)的結(jié)點進行搜索。2025/7/35三種搜索的優(yōu)劣之處一般來說，三種搜索方法各有優(yōu)劣之處：廣度優(yōu)先搜索的優(yōu)點是一定能找到解；缺點是空間復雜性和時間復雜性都大。深度優(yōu)先搜索的優(yōu)點是空間復雜性和時間復雜性較小；缺點是不一定能找到解。啟發(fā)式搜索是最好優(yōu)先的搜索，優(yōu)點是一般來說能較快地找到解，即其時間復雜性更小；缺點是需要設計一個評價函數(shù)，并且評價函數(shù)的優(yōu)劣決定了啟發(fā)式搜索的優(yōu)劣。2025/7/36樹搜索的一般形式SearchTree(SpaceT)//表L用來存放待考察的結(jié)點{unfinish=true;L=T.initial;//unfinish表示搜索未結(jié)束，先將初始狀態(tài)放入Lwhile(unfinish||L≠Φ){a=L.first;//從L中取出第一個元素if(aisgoal)unfinish=false//假設a是終態(tài)那么結(jié)束elseControl-put-in(L,Sons(a));}//否那么，將a的兒子們以某種控制方式放入L中2025/7/37三種搜索的不同之處

樹的三種搜索方法的不同就在于它們對表L使用了不同控制方式：L是一個隊列L是一個棧L的元素按照某方式排序廣度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)式搜索其中，深度優(yōu)先搜索就是回溯法。2025/7/38回溯法的形式化描述假設能夠用n元組〔x1,x2,…,xn〕表示一個給定的問題P的解，其中xi∈集合Si；n元組的子組〔x1,x2,…,xi〕〔i<n〕，如果它滿足一定的約束條件，那么稱為局部解。如果它已經(jīng)是滿足約束條件的局部解，那么添加xi+1∈Si+1形成新的子組〔x1,x2,…,xi,xi+1〕并檢查它是否滿足約束條件，假設滿足那么繼續(xù)添加xi+2∈Si+2，并以此類推。如果所有的xi+1∈Si+1都不滿足約束條件，那么去掉xi+1，回溯到xi的位置，并去掉當前的xi，另選一個xi’∈Si，組成新的子組〔x1,x2,…,xi’〕并判斷其是否滿足約束條件。如此反復下去，直到得到解或者證明無解為止。2025/7/39遞歸回溯法的一般形式Try(s){

做挑選候選者的準備；

while(未成功且還有候選者){

挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}

elseTry(s+1);if(不成功)刪去next的記錄;}}

return成功與否}2025/7/310迭代回溯法的一般形式先讓我們回憶解空間搜索的一般形式：SearchTree(SpaceT)//表L用來存放待考察的結(jié)點{unfinish=true;L=T.initial;//unfinish表示搜索未結(jié)束，先將初始狀態(tài)放入Lwhile(unfinish||L≠Φ){a=L.first;//從L中取出第一個元素if(aisgoal)finish=false//假設a是終態(tài)那么結(jié)束elseControl-put-in(L,Sons(a));}//否那么，將a的兒子們以某種控制方式放入L中回溯法中表L為棧，將初始狀態(tài)壓入棧中。彈出棧頂元素在通常求解問題時，解是由逐個狀態(tài)構(gòu)成的。因此，這里還需要判斷狀態(tài)是否可接受，并進行紀錄路徑等工作。如果a可接收但未終止，那么要將a的后繼壓入棧中。如果要拋棄狀態(tài)a，當a是最后一個兒子時，還需要消除原有紀錄甚至回溯一步。2025/7/311如何判斷最后一個兒子？假設只要遍歷解空間樹上的結(jié)點，那么將各個結(jié)點按棧的方式控制便可實現(xiàn)深度為主的搜索。但是在求解問題時，需要記錄解的路徑，在回溯時還需要刪除結(jié)點和修改相應的信息。棧中的結(jié)點是分層次的，而現(xiàn)在沒有區(qū)分它們的層次。這就增加了回溯判斷和操作的困難。那么怎么辦？采用一個簡潔有效的方法：設計一個末尾標記，每次壓棧時，先壓入末尾標記。2025/7/312用末尾標記的迭代回溯Backtrack(TreeT){unfinish=true;L.Push(T.root);while(unfinish||L≠Φ){a=L.Pop();if(aisthelastmark)backastep();else

if(aisgood){record(a);if(aisgoal){unfinish=false;output();}elseif(ahassons)L.Push-Sons(a)elsemove-off(a);}}}若棧頂元素是末尾標記，說明這個路徑已經(jīng)到頭了，需要回溯一步。若a是可以接受的，則將a加入求解的路徑中。若a是目標節(jié)點，則結(jié)束搜索并輸出求解的路徑。若a不是目標節(jié)點且a有后即，則將a的后繼壓入棧中。這里的L.Push-Sons(a)要先壓入末尾標記，然后再壓入后繼結(jié)點。若a不是目標節(jié)點又沒有后繼，則將a從解的路徑中刪除。2025/7/313不可接受的結(jié)點破壞了解的相容條件的結(jié)點超出了狀態(tài)空間的范圍，或者說不滿足約束條件的結(jié)點；評價值很差的結(jié)點，即已經(jīng)知道不可能獲得解的結(jié)點；已經(jīng)存在于被考察的路徑之中的結(jié)點，這種結(jié)點會造成搜索的死循環(huán)。2025/7/314數(shù)的全排列問題對于指定的n個數(shù)字，輸出它所有可能的排列。容易知道n個數(shù)字恰有n!個排列。它有一個隱含的約束條件：每個數(shù)字用且只能用一次。2025/7/315全排列問題的解空間樹設n=4，而需要排列的4個數(shù)字分別為：1，2，3，4?；貞浳覀兪止@四個數(shù)字的排列過程：〔1234〕

〔1243〕

〔1324〕

〔……………〕

〔4321〕

2025/7/316全排列問題中的數(shù)據(jù)表示數(shù)組rec[n+1]記錄當前搜索路徑上的每個結(jié)點所放置的數(shù)字；數(shù)組used[n+1]記錄當前搜索路徑上已經(jīng)被使用過的數(shù)字；2025/7/317用遞歸回溯法求N數(shù)全排列問題Try(s){

做挑選候選者的準備；

while(未成功且還有候選者){

挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}

elseTry(s+1);if(不成功)刪去next的記錄;}}

return成功與否}先回憶遞歸回溯法的一般形式：

2025/7/318用遞歸回溯法求N數(shù)全排列問題Try(s){

做挑選候選者的準備；

while(未成功且還有候選者){

挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}

elseTry(s+1);if(不成功)刪去next的記錄;}}

return成功與否}s為準備放置數(shù)字的位數(shù)候選者為數(shù)字1到n。j=0;q=0;令數(shù)字從j=0開始；q=0表示未成功。數(shù)字不到n就還有候選者(!q&&j<n){數(shù)字加1j++;假設數(shù)字沒有使用過，便可接受(Safe(j)){Record(s,j);(s=

=n){q=1;output(rec);}不成功，清掉該數(shù)字。(!q)Move-Off(s,j);}}}q}rec[s]=j;used[j]=1;(used[j]==0){(!q){rec[s]=0;used[j]=0;}}}n個位置都放完就成功了記下該位置的數(shù)字2025/7/319遞歸求全排列的主程序N-Arrange(){intrec[n+1],used[n+1];for(i=1,i<=n;i++){rec[i]=0;used[i]=0;}try(1);}從第一行開始遞歸2025/7/320N數(shù)全排列問題的迭代程序先看看迭代回溯法的一般形式：Backtrack(TreeT){

unfinish=true;L.Push(T.root);while(unfinish||L≠Φ){a=L.Pop();if(aisthelastmark)backastep();elseif(aisgood){record(a);if(aisgoal){unfinish=false;output();}elseif(ahassons)L.Push-Sons(a)elsemove-off(a);}}}迭代從第一個位置開始，將數(shù)字1~n和-1壓入棧中，這里-1作為末尾標記。i=1;L.Push(1,2,…,n,-1);a是末尾標記那么回溯。(a=

=-1)backastep;回溯需要做什么？回溯需要退回一個位置，即i––；同時刪除該位置的原紀錄。{i–

–;a=rec[i];Move-Off(i,a);}如果safe(a)那么放下數(shù)字a。(Safe(a))

{Record(i,a);如果到了第n位，那么成功。(i=

=n)當i<n時，那么必定有后繼。無需考慮此情況。{i++;L.Push(1,2,…,n,-1);}

}}}

2025/7/321N數(shù)全排列問題的迭代程序Backtrack(TreeT){unfinish=true;

i=1;L.Push(1,2,…,n,-1);while(unfinish||L≠Φ){a=L.Pop();if(a=

=-1){i––;a=rec[i];rec[i]=0;used[a]=0;}elseif(used[a]==0){rec[i]=a;used[a]=1;if(i==n){unfinish=false;output(rec);}else{i++;L.Push(1,2,…,n,-1);}}}}2025/7/322迭代求全排列主程序N-Queens(n){intrec[n+1],used[n+1];for(j=1,j<n+1;j++){rec[j]=0;used[j]=0;}Backtrack(n,rec);}2025/7/323N數(shù)全排列問題的時間復雜性對于規(guī)模為n的全排列而言,該算法的時間復雜度也就是搜索的結(jié)點總數(shù)。為簡單起見，只考慮訪問可擴展結(jié)點的時間。將根結(jié)點所在層次標為0層，其余依次為1,2,…,n層。那么每層的可擴展結(jié)點數(shù)目依次為：n,n(n-1),n(n-1)(n-2),……,n(n-1)……2,n!，設總的結(jié)點數(shù)目為S(n)，那么有

S(n)=∑n!/(k!)，故2n!≤S(n)≤3n!

故時間復雜度為O(n!)。2025/7/324N后問題要求在一個n×n的棋盤上放置n個皇后，使得她們彼此不受攻擊。按照國際象棋的規(guī)那么，一個皇后可以攻擊與之同一行或同一列或同一斜線上的任何棋子。因此，N后問題等價于：要求在一個n×n的棋盤上放置n個皇后，使得任意兩個皇后不得在同一行或同一列或同一斜線上。2025/7/325八皇后問題先建立一個8*8格的棋盤，在棋盤的第一行的任意位置安放第一只皇后。緊接著，我們就來放第二行，第二行的安放就要受一些限制了，因為與第一行的皇后在同一列或同一對角線的位置上是不能安放皇后的，接下來是第三行，……，或許我們會遇到這種情況：在擺到某一行的時候，無論皇后擺放在什么位置，她都會被其它行的皇后吃掉，這時就必須要回溯，將前面的皇后重新擺放，2025/7/326八皇后的一個可行解

第1列第2列第3列第4列第5列第6列第7列第8列記錄數(shù)組rec第1行○

1

第2行

○

7

第3行

○

5

第4行

○

8第5行

○

2

第6行

○

4

第7行

○

6

第8行

○

3

2025/7/327用遞歸回溯法求N后問題Try(s){

做挑選候選者的準備；

while(未成功且還有候選者){

挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}

elseTry(s+1);if(不成功)刪去next的記錄;}}

return成功與否}先回憶遞歸回溯法的一般形式：

2025/7/328用遞歸回溯法求N后問題Try(s){

做挑選候選者的準備；

while(未成功且還有候選者){

挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}

elseTry(s+1);if(不成功)刪去next的記錄;}}

return成功與否}s為準備放置后的行數(shù)候選者為1到n列。j=0;q=0;令列標記j=0；q表示未成功。列數(shù)不到n就還有候選者(!q&&j<n){列數(shù)加1j++;各后都平安，便可接受(Safe(s,j)){記下該行后的位置(列數(shù))Record(s,j);n行后都放完就成功了(s=

=n){q=1;output();}不成功，刪去后在該行的位置。(!q)Move-Off(s,j);}}}q}2025/7/329求解N后問題中的數(shù)據(jù)表示數(shù)組B[n]表示棋盤。假設B[i]=j，1≤i,j≤n，表示棋盤的第i行第j列上有皇后。數(shù)組C[j]=1表示第j列上無皇后，1≤j≤n。數(shù)組D[k]=1表示第k條下行(↘)對角線上無皇后。123456123456k=i+j，2≤k≤2n。這里，2025/7/330求解N后問題中的數(shù)據(jù)表示數(shù)組B[n]表示棋盤。假設B[i]=j，1≤i,j≤n，表示棋盤的第i行第j列上有皇后。數(shù)組C[j]=1表示第j列上無皇后，1≤j≤n。數(shù)組D[k]=1表示第k條下行(↘)對角線上無皇后。k=i+j，2≤k≤2n。這里，數(shù)組U[k]=1表示第k條上行(↗)對角線上無皇后。123456123456k=i–j，–n+1≤k≤n–1。這里，2025/7/331求解N后問題中的子程序Record(s,j){k=s–j+n–1;B[s]=j;C[j]=0;D[s+j–1]=0;U[k]=0;}Move-Off(s,j){k=s–j+n–1;B[s]=0;C[j]=1;D[s+j–1]=1;U[k]=1;}Safe(s,j){k=s–j+n–1;if(C[j]&&U[k]&&D[s+j–1])returntrueelsereturnfalse;}2025/7/332求解N后問題的主程序N-Queens(){intB[n+1],C[n+1],D[2n],U[2n];for(j=1,j<n+1;j++){B[j]=0;C[j]=1;U[2j]=1;U[2j–1]=1;D[2j]=1;D[2j–1]=1;}try(1);output(B);}將數(shù)組B[n],C[n],U[2n]和D[2n]都賦予初值。從第一行開始遞歸2025/7/333N后問題的迭代程序先看看迭代回溯法的一般形式：Backtrack(TreeT){

unfinish=true;L.Push(T.root);while(unfinish||L≠Φ){a=L.Pop();if(aisthelastmark)backastep();elseif(aisgood){record(a);if(aisgoal){unfinish=false;output();}elseif(ahassons)L.Push-Sons(a)elsemove-off(a);}}}迭代從第一行開始，將第一行的1~n列和0壓入棧中，這里0作為末尾標記。i=1;L.Push(1,2,…,n,0);a是末尾標記那么回溯。(a=

=0)backastep;回溯需要做什么？回溯需要退回一行，即i–

–；同時刪除該行的原紀錄。{i–

–;a=B[i];Move-Off(i,a);}如果safe(i,a)，那么放下后。(Safe(i,a))

{Record(i,a);如果到了第n行，那么成功。(i=

=n)當行i<n時，那么必定有后繼。無需考慮此情況。{i++;L.Push(1,2,…,n,0);}

}}}

2025/7/334N后問題的迭代程序Backtrack(TreeT){unfinish=true;

i=1;L.Push(1,2,…,n);while(unfinish||L≠Φ){a=L.Pop();if(a=

=0){i––;a=B[i];Move-Off(i,a);}elseif(Safe(i,a)){Record(i,a);if(i==n){unfinish=false;output(B);}else{i++;L.Push(1,2,…,n,0);}}}}2025/7/335迭代回溯解N后問題的主程序N-Queens(n){intB[n+1],C[n+1],D[2n],U[2n];for(j=1,j<n+1;j++){B[j]=0;C[j]=1;U[2j]=1;U[2j–1]=1;D[2j]=1;D[2j–1]=1;}Backtrack(n,B);}2025/7/336N后問題的時間復雜性如果只要找出N后問題的一個解，那么這是一個求路徑的問題。求路徑：只需要找到一條路徑便可以得到解。設每個狀態(tài)有k個后繼，其搜索樹為K叉樹，其結(jié)點總數(shù)為kn+1–1，遍歷的時間為O(kn)，這里n為找到解的路徑長度。N后問題的路徑深度為n，可選擇的后繼有n個，所以時間復雜性為O(nn)。2025/7/337旅行售貨員問題TSP：某售貨員到假設干城市去推銷商品，各城市之間的路程(或旅費)。他要選定一條路線，經(jīng)過每個城市一遍最后回到駐地的路線，使得總的路程(或總旅費)最小。設G=(V,E)是一個帶權(quán)圖。圖中各邊的費用(權(quán)值)為正。圖中一條周游路線是包括V中所有頂點的回路。一條周游路線的費用是該路線上所有邊的費用之和。所謂旅行售貨員問題就是要在圖G中找出一條最小費用的周游路線。2025/7/338Try(s){

做挑選候選者的準備；

while(未成功且還有候選者){

挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}

elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}線路上的第s個結(jié)點這里只需依次考察n–1個結(jié)點，即for(i=2;i<=n;i++)下一個候選就是i結(jié)點i尚未在路線中且總消耗值不大?？紤]TSP的遞歸回溯算法就是將結(jié)點i放入路線中并修改消耗值s=

=n假設新線路更好，就用新線路取代老線路。這里無所謂成功與否，因為每一條周游路線都要進行比較。2025/7/339TSP的遞歸回溯算法Try(s){for(i=2;i<=n;i++)if(Accept(i)){

Record(s,i)；if(s==n)

if(better)TakeNewPath();

elseTry(s+1);Move-off(s,i)}return}2025/7/340求解TSP的數(shù)據(jù)結(jié)構(gòu)用數(shù)組C[n][n]存放n個城市間的費用值。用數(shù)組P[n]記錄已經(jīng)找到的費用最小的周游路線，C為其相應的費用，C初值為∞。用數(shù)組N[n]記錄目前正在尋找的周游路線，NC為其相應的費用；如果NC+C[N[n]][1]小于C，那么路線N更佳，于是P[]=N[]，C=NC+C[N[n]][1]。如果結(jié)點next不是N中已有的結(jié)點，且C大于NC+C[N[i]][next]，那么結(jié)點next是可接受的。2025/7/341TSP的遞歸程序TryTry(s){for(i=2;i<=n;i++)if(Accept(i)){

Record(s,i)；if(s==n)

if(better)TakeNewPath();

elseTry(s+1);Move-off(s,i)}return}(C>NC+C[N[s]][i]

&&T[i]){數(shù)組T[]表示結(jié)點i尚未被選(C>NC+C[N[s]][1])TakeNewPath();

2025/7/342Try中的子程序Record(s,i);{NC=NC+C[N[s]][i];T[i]=0;N[s]=i;}Move-off(s,i);{NC=NC–C[N[s]][i];T[i]=1;N[s]=0;}TakeNewPath(){for(i=1;i<=n;i++)P[i]=N[i];C=NC+C[N[s]][1];}2025/7/343遞歸回溯求TSP的主程序TSP(n,C[n][n]){

for(i=1;i<=n;i++){N[i]=0;P[i]=0;T[i]=1}NC=0；C=∞;N[1]=1;T[1]=0;Try(1);Output(P)；}2025/7/344考慮TSP的迭代程序為了便于迭代程序中回溯的判斷，我們將城市結(jié)點編號為1~n，用編號0作為末尾的標記。先回憶一下采用末尾標記的迭代回溯法：2025/7/345考慮TSP的迭代程序Backtrack(TreeT){unfinish=true;L.Push(T.root);while(unfinish||L≠Φ){a=L.Pop();if(aisthelastmark)backastep();

elseif(aisgood){Record(a);if(aisgoal){unfinish=false;output();}elseif(ahassons)L.Push-Sons(a)elseMove-off(a);}}}要比較所有路徑，無需此句

L≠Φ){

初始化后壓入除1外的n-1個結(jié)點。N[1]=1;j=1;L.Push-Sons(2,…,n,0);

末尾標記為0。(a=

=0)backastep();刪除第j個結(jié)點，然后j––.{Move-off(N[j–1],

N[j]);j–

–;}a不在路線中且新增后的費用仍低。(T[a]&&C–NC>C[N[j]][a]){Record(N[j],a);已經(jīng)n個結(jié)點且新路線的費用更低。這個判斷不需要了(j==n){if(C>NC+C[a][1]){TakeNewPath();Move-off(N[j],a);}}else{j++;L.Push-Sons(2,…,n,0)}}}2025/7/346TSP的迭代回溯Backtrack(n,C){j=1;N[j]=1;L.Push-Sons(2,…,n,0);while(L≠Φ){a=L.Pop();if(a=

=0){Move-off(N[j–1],

N[j]);j–

–;}elseif(T[a]&&C–NC>C[N[j]][a])

{Record(N[j],a)；if(j==n){if(C>NC+C[a][1]){TakeNewPath();Move-off(N[j],a);}}

else{j++;L.Push-Sons(2,…,n,0)}}}2025/7/347Backtrack中的子程序Record(N[j],a);

{NC=NC+C[N[j]][a];T[a]=0;N[j+1]=a;}Move-off(N[j],a);

{NC=NC–C[N[j]][a];T[a]=1;N[j+1]=0;}TakeNewPath(){for(i=1;i<=n;i++)P[i]=N[i];C=NC+C[N[j]][1];}2025/7/348迭代回溯求TSP的主程序TSP(n,C[n][n]){

for(i=1;i<=n;i++){N[i]=0;P[i]=0;T[i]=1}NC=0；C=∞;N[1]=1;T[1]=0;Backtrack(n,C);Output(P)；}2025/7/349求解TSP的時間復雜性顯然TSP是一個求排列的問題。求排列：確定n個元素的滿足某種性質(zhì)的排列。其搜索樹稱為排列樹，通常有n!個葉結(jié)點，因此遍歷排列樹需要時間為O(n!)。所以TSP問題的時間復雜性為O(n!)2025/7/3500-1背包問題給定n個物品和一個背包。物品i的重量為wi，價值為vi，背包容量為c。問如何選擇裝入背包中的物品，使得裝入背包的物品的價值最大？在裝入背包時，每種物品i只有兩種選擇，裝入或者不裝入，既不能裝入屢次，也不能只裝入一局部。因此，此問題稱為0-1背包問題。如果在裝入背包時，物品可以切割，即可以只裝入一局部，這種情況下的問題稱為背包問題。2025/7/351用回溯法解0-1背包問題類似于旅行售貨員問題，用一個數(shù)組P[n]存放目前取得的最優(yōu)解，用變量V表示其價值；再用一個數(shù)組N[n]來產(chǎn)生新的解，用變量NV表示其價值，用變量W表示其重量。如果新解更優(yōu)，那么替代原來的最優(yōu)解，否那么就丟棄新解。然后回溯尋找下一個新解。為此，我們先回憶一下回溯法的一般遞歸算法：2025/7/352用回溯法解0-1背包問題Try(s){

做挑選候選者的準備；

while(未成功且還有候選者){

挑選下一個候選者next；if(next可接受){記錄next；if(滿足成功條件){成功并輸出結(jié)果}

elseTry(s+1);if(不成功)刪去next的記錄;}}return成功與否}考察的第s個物品只需考兩種情況，選或不選，即for(i=0;i<2;i++)下個候選就是i。物體s可放入背包中；將s放入背包中并修改權(quán)重與容量；s=

=n這里無論成功與否都要繼續(xù)考察“記錄〞的逆操作2025/7/353用回溯法解0-1背包問題Try(s){for(i=0;i<2;i++)if(Accept(i)){

Record(s,i)；if(s==n){if(better)TakeNewChoice();}

elseTry(s+1);Move-off(s,i);}return}(W+w[s]*i<=C){(NV>V)2025/7/3540-1背包問題中的幾個子程序Record(s,i){N[s]=i;W=W+w[s]*i;NV=NV+v[s]*i;}Move-off(s,i){N[s]=0;W=W–w[s]*i;NV=NV–v[s]*i;}TakeNewChoice(){for(i=1;i<=n;i++){P[i]=N[i];V=NV;}}2025/7/3550-1背包問題的主程序Bag(n,C,w[n],v[n]){

for(i=1;i<=n;i++){N[i]=0;P[i]=0;T[i]=1;}NV=0,W=0;V=0;Try(1);Output(P);}2025/7/356考慮0-1背包問題的迭代實現(xiàn)先看看回溯法的一般的迭代形式：

Backtrack(TreeT){

unfinish=true;L.Push(T.root);while(unfinish||L≠Φ){a=L.Pop();