回溯演算法解題模板

㈠ 求C語言中的回溯法，舉一個簡單的小例子，說明回溯法的運行過程！

求子串位置
int Index(SString S, SString T, int pos) {
// 返回子串T在主串S中第pos個字元之後的位置。
// 若不存在，則函數值為0。
// 其中，T非空，1≤pos≤StrLength(S)。
int i = pos;
int j = 1;
while (i <= S[0] && j <= T[0]) {
if (S[i] == T[j]) { // 繼續比較後繼字元
++i;
++j;
} else { // 指針後退重新開始匹配
i = i-j+2;
j = 1;
}
}
if (j > T[0]) return i-T[0];
else return 0;
} // Index

㈡ 什麼是回溯演算法

回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。用回溯演算法解決問題的一般步驟為： 1、定義一個解空間，它包含問題的解。 2、利用適於搜索的方法組織解空間。 3、利用深度優先法搜索解空間。 4、利用限界函數避免移動到不可能產生解的子空間。 問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯演算法的一個重要特性。 1.跳棋問題： 33個方格頂點擺放著32枚棋子，僅中央的頂點空著未擺放棋子。下棋的規則是任一棋子可以沿水平或成垂直方向跳過與其相鄰的棋子，進入空著的頂點並吃掉被跳過的棋子。試設計一個演算法找出一種下棋方法，使得最終棋盤上只剩下一個棋子在棋盤中央。 演算法實現提示 利用回溯演算法，每次找到一個可以走的棋子走動，並吃掉。若走到無子可走還是剩餘多顆，則回溯，走下一顆可以走動的棋子。當吃掉31顆時說明只剩一顆，程序結束。 2.中國象棋馬行線問題： 中國象棋半張棋盤如圖1(a)所示。馬自左下角往右上角跳。今規定只許往右跳，不許往左跳。比如 圖4（a）中所示為一種跳行路線，並將所經路線列印出來。列印格式為： 0，0->2,1->3,3->1,4->3,5->2,7->4,8… 演算法分析： 如圖1(b),馬最多有四個方向，若原來的橫坐標為j、縱坐標為i,則四個方向的移動可表示為： 1: （i,j）→（i+2,j+1）； (i<3,j<8) 2: （i,j）→（i+1,j+2）； (i<4,j<7) 3: （i,j）→（i-1,j+2）； (i>0,j<7) 4: （i,j）→（i-2,j+1）； (i>1,j<8) 搜索策略： S1:Ａ[１]:=(0,0); S2:從Ａ[1]出發，按移動規則依次選定某個方向，如果達到的是（4,8）則轉向S3,否則繼續搜索下 一個到達的頂點； S3:列印路徑。 演算法設計： procere try(i:integer); {搜索} var j:integer; begin for j:=1 to 4 do {試遍4個方向} if 新坐標滿足條件 then begin 記錄新坐標; if 到達目的地 then print {統計方案，輸出結果} else try(i+1); {試探下一步} 退回到上一個坐標，即回溯; end; end;

㈢ 24點問題，回溯演算法

回溯演算法也叫試探法，它是一種系統地搜索問題的解的方法。回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。用回溯演算法解決問題的一般步驟為： 1、定義一個解空間，它包含問題的解。 2、利用適於搜索的方法組織解空間。 3、利用深度優先法搜索解空間。 4、利用限界函數避免移動到不可能產生解的子空間。 問題的解空間通常是在搜索問題的解的過程中動態產生的，這是回溯演算法的一個重要特性。1.跳棋問題：33個方格頂點擺放著32枚棋子，僅中央的頂點空著未擺放棋子。下棋的規則是任一棋子可以沿水平或成垂直方向跳過與其相鄰的棋子，進入空著的頂點並吃掉被跳過的棋子。試設計一個演算法找出一種下棋方法，使得最終棋盤上只剩下一個棋子在棋盤中央。演算法實現提示利用回溯演算法，每次找到一個可以走的棋子走動，並吃掉。若走到無子可走還是剩餘多顆，則回溯，走下一顆可以走動的棋子。當吃掉31顆時說明只剩一顆，程序結束。2.中國象棋馬行線問題：中國象棋半張棋盤如圖1(a)所示。馬自左下角往右上角跳。今規定只許往右跳，不許往左跳。比如圖4（a）中所示為一種跳行路線，並將所經路線列印出來。列印格式為：0，0->2,1->3,3->1,4->3,5->2,7->4,8…演算法分析：如圖1(b),馬最多有四個方向，若原來的橫坐標為j、縱坐標為i,則四個方向的移動可表示為：1: （i,j）→（i+2,j+1）； (i<3,j<8) 2: （i,j）→（i+1,j+2）； (i<4,j<7)3: （i,j）→（i-1,j+2）； (i>0,j<7) 4: （i,j）→（i-2,j+1）； (i>1,j<8)搜索策略：S1:Ａ[１]:=(0,0);S2:從Ａ[1]出發，按移動規則依次選定某個方向，如果達到的是（4,8）則轉向S3,否則繼續搜索下一個到達的頂點；S3:列印路徑。演算法設計：procere try(i:integer); var j:integer;beginfor j:=1 to 4 do if 新坐標滿足條件 thenbegin記錄新坐標;if 到達目的地 then print else try(i+1); 退回到上一個坐標，即回溯;end;end;

㈣ 簡述回溯法的2種演算法框架,並分別舉出適合用這兩種框架解決的一個問題實例

回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。
基本思想
在包含問題的所有解的解空間樹中，按照深度優先搜索的策略，從根結點出發深度探索解空間樹。當探索到某一結點時，要先判斷該結點是否包含問題的解，如果包含，就從該結點出發繼續探索下去，如果該結點不包含問題的解，則逐層向其祖先結點回溯。（其實回溯法就是對隱式圖的深度優先搜索演算法）。 若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束。 而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束

一般表達
可用回溯法求解的問題P，通常要能表達為：對於已知的由n元組（x1，x2，…，xn）組成的一個狀態空間E={（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n}，給定關於n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且 |Si| 有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。
解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。

規律
我們發現，對於許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（j<=i）元組（x1，x2，…，xj）一定也滿足d中僅涉及到x1，x2，…，xj的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x1，x2，…，xj）違反d中僅涉及到x1，x2，…，xj的約束之一，則以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）一定也違反d中僅涉及到x1，x2，…，xi的一個約束，n≥i≥j。因此，對於約束集d具有完備性的問題p，一旦檢測斷定某個j元組（x1，x2，…，xj）違反d中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題p的解，因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的演算法。

㈤ 用遞歸回溯法設計旅行售貨員問題的演算法

一、回溯法：
回溯法是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。

二、演算法框架：
1、問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。

2、回溯法的基本思想：確定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，並成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
運用回溯法解題通常包含以下三個步驟：
（1）針對所給問題，定義問題的解空間；
（2）確定易於搜索的解空間結構；
（3）以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索；

3、遞歸回溯：由於回溯法是對解空間的深度優先搜索，因此在一般情況下可用遞歸函數來實現回溯法如下：
procere try(i:integer);
var
begin
if i>n then 輸出結果
else for j:=下界 to 上界 do
begin
x[i]:=h[j];
if 可行{滿足限界函數和約束條件} then begin 置值；try(i+1); end;
end;
end;

說明：
i是遞歸深度；
n是深度控制，即解空間樹的的高度；
可行性判斷有兩方面的內容：不滿約束條件則剪去相應子樹；若限界函數越界，也剪去相應子樹；兩者均滿足則進入下一層；

搜索：全面訪問所有可能的情況，分為兩種：不考慮給定問題的特有性質，按事先頂好的順序，依次運用規則，即盲目搜索的方法；另一種則考慮問題給定的特有性質，選用合適的規則，提高搜索的效率，即啟發式的搜索。
回溯即是較簡單、較常用的搜索策略。
基本思路：若已有滿足約束條件的部分解，不妨設為（x1,x2,x3,……xi），I<n,則添加x(i+1)屬於s(i+2)，檢查(x1,x2,……,xi,x(i+1))是否滿足條件，滿足了就繼續添加x(i+2)、s(i+2)，若所有的x(i+1)屬於s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察過的x1屬於s1，看其是否滿足約束條件，為此反復進行，直至得到解或證明無解。

㈥ 0-1背包問題的多種解法代碼（動態規劃、貪心法、回溯法、分支限界法）

一.動態規劃求解0-1背包問題
/************************************************************************/
/* 0-1背包問題：
/* 給定n種物品和一個背包
/* 物品i的重量為wi，其價值為vi
/* 背包的容量為c
/* 應如何選擇裝入背包的物品，使得裝入背包中的物品
/* 的總價值最大？
/* 註：在選擇裝入背包的物品時，對物品i只有兩種選擇，
/* 即裝入或不裝入背包。不能將物品i裝入多次，也
/* 不能只裝入部分的物品i。
/*
/* 1. 0-1背包問題的形式化描述：
/* 給定c>0, wi>0, vi>0, 0<=i<=n，要求找到一個n元的
/* 0-1向量(x1, x2, ..., xn), 使得：
/* max sum_{i=1 to n} (vi*xi),且滿足如下約束：
/* (1) sum_{i=1 to n} (wi*xi) <= c
/* (2) xi∈{0, 1}, 1<=i<=n
/*
/* 2. 0-1背包問題的求解
/* 0-1背包問題具有最優子結構性質和子問題重疊性質，適於
/* 採用動態規劃方法求解
/*
/* 2.1 最優子結構性質
/* 設(y1,y2,...,yn)是給定0-1背包問題的一個最優解，則必有
/* 結論，(y2,y3,...,yn)是如下子問題的一個最優解：
/* max sum_{i=2 to n} (vi*xi)
/* (1) sum_{i=2 to n} (wi*xi) <= c - w1*y1
/* (2) xi∈{0, 1}, 2<=i<=n
/* 因為如若不然，則該子問題存在一個最優解(z2,z3,...,zn)，
/* 而(y2,y3,...,yn)不是其最優解。那麼有：
/* sum_{i=2 to n} (vi*zi) > sum_{i=2 to n} (vi*yi)
/* 且，w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 進一步有：
/* v1*y1 + sum_{i=2 to n} (vi*zi) > sum_{i=1 to n} (vi*yi)
/* w1*y1 + sum_{i=2 to n} (wi*zi) <= c
/* 這說明：(y1,z2,z3,...zn)是所給0-1背包問題的更優解，那麼
/* 說明(y1,y2,...,yn)不是問題的最優解，與前提矛盾，所以最優
/* 子結構性質成立。
/*
/* 2.2 子問題重疊性質
/* 設所給0-1背包問題的子問題 P(i,j)為：
/* max sum_{k=i to n} (vk*xk)
/* (1) sum_{k=i to n} (wk*xk) <= j
/* (2) xk∈{0, 1}, i<=k<=n
/* 問題P(i,j)是背包容量為j、可選物品為i,i+1,...,n時的子問題
/* 設m(i,j)是子問題P(i,j)的最優值，即最大總價值。則根據最優
/* 子結構性質，可以建立m(i,j)的遞歸式：
/* a. 遞歸初始 m(n,j)
/* //背包容量為j、可選物品只有n，若背包容量j大於物品n的
/* //重量，則直接裝入；否則無法裝入。
/* m(n,j) = vn, j>=wn
/* m(n,j) = 0, 0<=j<wn
/* b. 遞歸式 m(i,j)
/* //背包容量為j、可選物品為i,i+1,...,n
/* //如果背包容量j<wi，則根本裝不進物品i，所以有：
/* m(i,j) = m(i+1,j), 0<=j<wi
/* //如果j>=wi，則在不裝物品i和裝入物品i之間做出選擇
/* 不裝物品i的最優值：m(i+1,j)
/* 裝入物品i的最優值：m(i+1, j-wi) + vi
/* 所以：
/* m(i,j) = max {m(i+1,j), m(i+1, j-wi) + vi}, j>=wi
/*
/************************************************************************/

#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
template <typename Type>
void Knapsack(Type* v, int *w, int c, int n, Type **m)
{
//遞歸初始條件
int jMax = min(w[n] - 1, c);
for (int j=0; j<=jMax; j++) {
m[n][j] = 0;
}

for (j=w[n]; j<=c; j++) {
m[n][j] = v[n];
}

//i從2到n-1，分別對j>=wi和0<=j<wi即使m(i,j)
for (int i=n-1; i>1; i--) {
jMax = min(w[i] - 1, c);
for (int j=0; j<=jMax; j++) {
m[i][j] = m[i+1][j];
}
for (j=w[i]; j<=c; j++) {
m[i][j] = max(m[i+1][j], m[i+1][j-w[i]]+v[i]);
}
}

m[1][c] = m[2][c];
if (c >= w[1]) {
m[1][c] = max(m[1][c], m[2][c-w[1]]+v[1]);
}

}

template <typename Type>
void TraceBack(Type **m, int *w, int c, int n, int* x)
{
for (int i=1; i<n; i++) {
if(m[i][c] == m[i+1][c]) x[i] = 0;
else {
x[i] = 1;
c -= w[i];
}
}
x[n] = (m[n][c])? 1:0;
}

int main(int argc, char* argv[])
{
int n = 5;
int w[6] = {-1, 2, 2, 6, 5, 4};
int v[6] = {-1, 6, 3, 5, 4, 6};
int c = 10;

int **ppm = new int*[n+1];
for (int i=0; i<n+1; i++) {
ppm[i] = new int[c+1];
}

int x[6];

Knapsack<int>(v, w, c, n, ppm);
TraceBack<int>(ppm, w, c, n, x);

return 0;
}
二.貪心演算法求解0-1背包問題
1.貪心法的基本思路：
——從問題的某一個初始解出發逐步逼近給定的目標，以盡可能快的地求得更好的解。當達到某演算法中的某一步不能再繼續前進時，演算法停止。
該演算法存在問題：
1).不能保證求得的最後解是最佳的；
2).不能用來求最大或最小解問題；
3).只能求滿足某些約束條件的可行解的范圍。

實現該演算法的過程：
從問題的某一初始解出發；
while 能朝給定總目標前進一步 do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；

2.例題分析

1).[背包問題]有一個背包，背包容量是M=150。有7個物品，物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。

物品 A B C D E F G
重量 35 30 60 50 40 10 25
價值 10 40 30 50 35 40 30

分析：
目標函數： ∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M( M=150)
（1）根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
（2）每次挑選所佔空間最小的物品裝入是否能得到最優解？
（3）每次選取單位容量價值最大的物品，成為解本題的策略。

<程序代碼:>(環境:c++)
#include<iostream.h>
#define max 100 //最多物品數
void sort (int n,float a[max],float b[max]) //按價值密度排序
{
int j,h,k;
float t1,t2,t3,c[max];
for(k=1;k<=n;k++)
c[k]=a[k]/b[k];
for(h=1;h<n;h++)
for(j=1;j<=n-h;j++)
if(c[j]<c[j+1])
{t1=a[j];a[j]=a[j+1];a[j+1]=t1;
t2=b[j];b[j]=b[j+1];b[j+1]=t2;
t3=c[j];c[j]=c[j+1];c[j+1]=t3;
}
}
void knapsack(int n,float limitw,float v[max],float w[max],int x[max])
{float c1; //c1為背包剩餘可裝載重量
int i;
sort(n,v,w); //物品按價值密度排序
c1=limitw;
for(i=1;i<=n;i++)
{
if(w[i]>c1)break;
x[i]=1; //x[i]為1時，物品i在解中
c1=c1-w[i];
}
}
void main()
{int n,i,x[max];
float v[max],w[max],totalv=0,totalw=0,limitw;
cout<<"請輸入n和limitw:";
cin>>n >>limitw;
for(i=1;i<=n;i++)
x[i]=0; //物品選擇情況表初始化為0
cout<<"請依次輸入物品的價值："<<endl;
for(i=1;i<=n;i++)
cin>>v[i];
cout<<endl;
cout<<"請依次輸入物品的重量："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];
cout<<endl;
knapsack (n,limitw,v,w,x);
cout<<"the selection is:";
for(i=1;i<=n;i++)
{
cout<<x[i];
if(x[i]==1)
totalw=totalw+w[i];
}
cout<<endl;
cout<<"背包的總重量為："<<totalw<<endl; //背包所裝載總重量
cout<<"背包的總價值為："<<totalv<<endl; //背包的總價值
}
三.回溯演算法求解0-1背包問題
1.0-l背包問題是子集選取問題。
一般情況下，0-1背包問題是NP難題。0-1背包
問題的解空間可用子集樹表示。解0-1背包問題的回溯法與裝載問題的回溯法十分類
似。在搜索解空間樹時，只要其左兒子結點是一個可行結點，搜索就進入其左子樹。當
右子樹有可能包含最優解時才進入右子樹搜索。否則將右子樹剪去。設r是當前剩餘
物品價值總和；cp是當前價值；bestp是當前最優價值。當cp+r≤bestp時，可剪去右
子樹。計算右子樹中解的上界的更好方法是將剩餘物品依其單位重量價值排序，然後
依次裝入物品，直至裝不下時，再裝入該物品的一部分而裝滿背包。由此得到的價值是
右子樹中解的上界。
2.解決辦法思路：
為了便於計算上界，可先將物品依其單位重量價值從大到小排序，此後只要順序考
察各物品即可。在實現時，由bound計算當前結點處的上界。在搜索解空間樹時，只要其左兒子節點是一個可行結點，搜索就進入左子樹，在右子樹中有可能包含最優解是才進入右子樹搜索。否則將右子樹剪去。

回溯法是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。
2.演算法框架：
a.問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。
b.回溯法的基本思想：確定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，並成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
3.運用回溯法解題通常包含以下三個步驟：
a.針對所給問題，定義問題的解空間；
b.確定易於搜索的解空間結構；
c.以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索；
#include<iostream>

using namespace std;

class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );

public:
void print()
{

for(int m=1;m<=n;m++)
{
cout<<bestx[m]<<" ";
}
cout<<endl;
};

private:
int Bound(int i);
void Backtrack(int i);

int c;//背包容量
int n; //物品數
int *w;//物品重量數組
int *p;//物品價值數組
int cw;//當前重量
int cp;//當前價值
int bestp;//當前最優值
int *bestx;//當前最優解
int *x;//當前解

};

int Knap::Bound(int i)
{
//計算上界
int cleft=c-cw;//剩餘容量
int b=cp;
//以物品單位重量價值遞減序裝入物品
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
b+=p[i];
i++;
}
//裝滿背包
if(i<=n)
b+=p[i]/w[i]*cleft;
return b;
}

void Knap::Backtrack(int i)
{
if(i>n)
{
if(bestp<cp)
{
for(int j=1;j<=n;j++)
bestx[j]=x[j];
bestp=cp;
}
return;
}
if(cw+w[i]<=c) //搜索左子樹
{
x[i]=1;
cw+=w[i];
cp+=p[i];
Backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(Bound(i+1)>bestp)//搜索右子樹
{
x[i]=0;
Backtrack(i+1);
}

}

class Object
{
friend int Knapsack(int p[],int w[],int c,int n);
public:
int operator<=(Object a)const
{
return (d>=a.d);
}

private:
int ID;
float d;
};

int Knapsack(int p[],int w[],int c,int n)
{
//為Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P;//裝入所有物品
//依物品單位重量排序
float f;
for( i=0;i<n;i++)
for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
}

}

Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);
K.print();
delete [] Q;
delete [] K.w;
delete [] K.p;
return K.bestp;

}

void main()
{
int *p;
int *w;
int c=0;
int n=0;
int i=0;
char k;
cout<<"0-1背包問題——回溯法 "<<endl;
cout<<" by zbqplayer "<<endl;
while(k)
{
cout<<"請輸入背包容量(c)："<<endl;
cin>>c;
cout<<"請輸入物品的個數(n)："<<endl;
cin>>n;
p=new int[n+1];
w=new int[n+1];
p[0]=0;
w[0]=0;

cout<<"請輸入物品的價值(p)："<<endl;
for(i=1;i<=n;i++)
cin>>p[i];

cout<<"請輸入物品的重量(w)："<<endl;
for(i=1;i<=n;i++)
cin>>w[i];

cout<<"最優解為(bestx)："<<endl;
cout<<"最優值為(bestp)："<<endl;
cout<<Knapsack(p,w,c,n)<<endl;
cout<<"[s] 重新開始"<<endl;
cout<<"[q] 退出"<<endl;
cin>>k;
}
四.分支限界法求解0-1背包問題
1.問題描述：已知有N個物品和一個可以容納M重量的背包，每種物品I的重量為WEIGHT，一個只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的總效益最大。

2.設計思想與分析：對物品的選取與否構成一棵解樹，左子樹表示不裝入，右表示裝入，通過檢索問題的解樹得出最優解，並用結點上界殺死不符合要求的結點。

#include <iostream.h>

struct good
{
int weight;
int benefit;
int flag;//是否可以裝入標記
};

int number=0;//物品數量
int upbound=0;
int curp=0, curw=0;//當前效益值與重量
int maxweight=0;
good *bag=NULL;

void Init_good()
{
bag=new good [number];

for(int i=0; i<number; i++)
{
cout<<"請輸入第件"<<i+1<<"物品的重量:";
cin>>bag[i].weight;
cout<<"請輸入第件"<<i+1<<"物品的效益:";
cin>>bag[i].benefit;
bag[i].flag=0;//初始標志為不裝入背包
cout<<endl;
}

}

int getbound(int num, int *bound_u)//返回本結點的c限界和u限界
{
for(int w=curw, p=curp; num<number && (w+bag[num].weight)<=maxweight; num++)
{
w=w+bag[num].weight;
p=w+bag[num].benefit;
}

*bound_u=p+bag[num].benefit;
return ( p+bag[num].benefit*((maxweight-w)/bag[num].weight) );
}

void LCbag()
{
int bound_u=0, bound_c=0;//當前結點的c限界和u限界

for(int i=0; i<number; i++)//逐層遍歷解樹決定是否裝入各個物品
{
if( ( bound_c=getbound(i+1, &bound_u) )>upbound )//遍歷左子樹
upbound=bound_u;//更改已有u限界,不更改標志

if( getbound(i, &bound_u)>bound_c )//遍歷右子樹
//若裝入，判斷右子樹的c限界是否大於左子樹根的c限界，是則裝入
{
upbound=bound_u;//更改已有u限界
curp=curp+bag[i].benefit;
curw=curw+bag[i].weight;//從已有重量和效益加上新物品
bag[i].flag=1;//標記為裝入
}
}

}

void Display()
{

cout<<"可以放入背包的物品的編號為：";
for(int i=0; i<number; i++)
if(bag[i].flag>0)
cout<<i+1<<" ";
cout<<endl;
delete []bag;
}

㈦ 回溯法的基本思想是什麼

回溯法又稱試探法。回溯法的基本做法是深度優先搜索，是一種組織得井井有條的、能避免不必要重復搜索的窮舉式搜索演算法。
回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
當我們遇到某一類問題時，它的問題可以分解，但是又不能得出明確的動態規劃或是遞歸解法，此時可以考慮用回溯法解決此類問題。回溯法的優點在於其程序結構明確，可讀性強，易於理解，而且通過對問題的分析可以大大提高運行效率。但是，對於可以得出明顯的遞推公式迭代求解的問題，還是不要用回溯法，因為它花費的時間比較長。
對於用回溯法求解的問題，首先要將問題進行適當的轉化，得出狀態空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過深度優先搜索這棵樹，枚舉每種可能的解的情況；從而得出結果。但是，回溯法中通過構造約束函數，可以大大提升程序效率，因為在深度優先搜索的過程中，不斷的將每個解（並不一定是完整的，事實上這也就是構造約束函數的意義所在）與約束函數進行對照從而刪除一些不可能的解，這樣就不必繼續把解的剩餘部分列出從而節省部分時間。
回溯法中，首先需要明確下面三個概念：
（一）約束函數：約束函數是根據題意定出的。通過描述合法解的一般特徵用於去除不合法的解，從而避免繼續搜索出這個不合法解的剩餘部分。因此，約束函數是對於任何狀態空間樹上的節點都有效、等價的。
（二）狀態空間樹：剛剛已經提到，狀態空間樹是一個對所有解的圖形描述。樹上的每個子節點的解都只有一個部分與父節點不同。
（三）擴展節點、活結點、死結點：所謂擴展節點，就是當前正在求出它的子節點的節點，在深度優先搜索中，只允許有一個擴展節點。活結點就是通過與約束函數的對照，節點本身和其父節點均滿足約束函數要求的節點；死結點反之。由此很容易知道死結點是不必求出其子節點的（沒有意義）。
利用回溯法解題的具體步驟
首先，要通過讀題完成下面三個步驟：
(1)描述解的形式，定義一個解空間，它包含問題的所有解。
(2)構造狀態空間樹。
(3)構造約束函數（用於殺死節點）。

然後就要通過深度優先搜索思想完成回溯，完整過程如下：
(1)設置初始化的方案（給變數賦初值，讀入已知數據等）。
(2)變換方式去試探，若全部試完則轉(7)。
(3)判斷此法是否成功（通過約束函數），不成功則轉(2)。
(4)試探成功則前進一步再試探。
(5)正確方案還未找到則轉(2)。
(6)已找到一種方案則記錄並列印。
(7)退回一步（回溯），若未退到頭則轉(2)。
(8)已退到頭則結束或列印無解

㈧ 回溯法的用回溯法解題的一般步驟

（1）針對所給問題，定義問題的解空間；
（2）確定易於搜索的解空間結構；
（3）以深度優先方式搜索解空間，並在搜索過程中用剪枝函數避免無效搜索。
回溯法C語言舉例
八皇後問題是能用回溯法解決的一個經典問題。
八皇後問題是一個古老而著名的問題。該問題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一對角線上，問有多少種擺法。引入一個整型一維數組col[]來存放最終結果，col[i]就表示在棋盤第i列、col[i]行有一個皇後，為了使程序再找完了全部解後回到最初位置，設定col[0]的初值為0，即當回溯到第0列時，說明以求得全部解，結束程序運行。為了方便演算法的實現，引入三個整型數組來表示當前列在三個方向上的狀態 ：
a[] a[i]=0表示第i行上還沒有皇後；
b[] b[i]=0表示第i列反斜線/上沒有皇後；
c[] c[i]=0表示第i列正斜線上沒有皇後。
棋盤中同一反斜線/上的方格的行號與列號之和相同；同一正斜線上的方格的行號與列號之差均相同，這就是判斷斜線的依據。
初始時，所有行和斜線上都沒有皇後，從第1列的第1行配置第一個皇後開始，在第m列，col[m]行放置了一個合理的皇後，准備考察第m+1列時，在數組a[]，b[]和c[]中為第m列，col[m]行的位置設定有皇後的標志；當從第m列回溯到m-1列時，並准備調整第m-1列的皇後配置時，清除在數組a[],b[]和c[]對應位置的值都為1來確定。 #include<stdio.h>
#include<stdlib.h>
#define Queens 8
int a[Queens+1]; //八皇後問題的皇後所在每一行位置，從1開始算
int main()
{
int i,k,flag,not_finish=1,count=0;
i=1;//初始
a[1]=1;
printf(the possible configuration of 8 queesns are: );
while(not_finish) //not_finsh=1:處理未結束
{
while(not_finish && i<Queens+1) //處理未結束
{
for(flag=1,k=1;flag && k<i;k++)//判斷是否有多個皇後在同一行
if(a[k]==a[i])
flag=0;
for(k=1;flag && k<i;k++) //判斷是否有多個皇後在對角線
if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i)))
flag=0;
if(!flag) //若存在矛盾 重設第i個元素
{
if(a[i]==a[i-1]) //若a[i]的值已經已經一圈追上a[i-1]的值
{
i--; //退回一步 重新試探處理前一個元素
if(i>1 && a[i]==Queens)
a[i]=1; // 當a[i]為 Queens時 將a[i]的值重置
else
if(i==1 && a[i]==Queens)//當第一未位的值達到Queens時結束
not_finish=0;
else
a[i]++;
}
else
if(a[i]==Queens)
a[i]=1;
else
a[i]++;
}
else
if(++i<=Queens) //若前一個元素的值為Queens
if(a[i-1]==Queens)
a[i]=1;
else //否則元素為前一個元素的下一個值
a[i]=a[i-1]+1;
}
if (not_finish)
{
++count;
printf((count-1)%3?[%2d]:: [%2d]:,count);
for(k=1;k<=Queens;k++) //輸出結果
printf(%d,a[k]);
if(a[Queens-1]<Queens)
a[Queens-1]++;
else
a[Queens-1]=1;
i=Queens-1;
}
}
system(pause);
} var
n,k,t,i:longint;
x:array[1..100] of integer;
function pa(k:integer):boolean;
begin
pa:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then pa:=false;
end;
procere try(k:integer);
var
i:integer;
begin
if k>n then
begin
t:=t+1;
exit;
end;
for i:=1 to n do
begin
x[k]:=i;
if pa(k) then try(k+1);
end;
end;
begin
read(n);
t:=0;
try(1);
write(t);
end. #include
#include
#define m 5
#define n 6
int sf=0;
int mase[m][n]={{0,0,0,1,0,0},{0,1,0,0,0,0},{0,1,1,1,1,0},{0,0,0,0,0,1},{1,0,1,1,0,0}};
void search(int x,int y)
{
if((x==m-1)&&(y==n-1))
sf=1;
else
{
mase[x][y]=1;
if((sf!=1)&&(y!=n-1)&&mase[x][y+1]==0)
search(x,y+1);
if((sf!=1)&&(x!=m-1)&&mase[x+1][y]==0)
search(x+1,y);
if((sf!=1)&&(y!=0)&&mase[x][y-1]==0)
search(x,y-1);
if((sf!=1)&&(x!=0)&&mase[x-1][y]==0)
search(x-1,y);
}
mase[x][y]=0;
if(sf==1)
mase[x][y]=5;//通過路徑用數字的表示
}
int main()
{
int i=0,j=0;
//clrscr();
search(0,0);
for(i=0;i<m;i++) p=></m;i++)>
{
for(j=0;j<n;j++) p=></n;j++)>
printf(%d,mase[i][j]);
printf( );
}
system(pause);
return 0;
}
回溯法解決迷宮問題PASCAL語言
program migong;
var
n,k,j,x,y:integer;
a:array[0..10000,0..10000] of integer;
b:array[0..1000000,0..2] of integer;
procere search(x,y,i:integer);
begin
a[x,y]:=1;
if (x=n) and (y=n) then
begin
for j:=1 to i-1 do
writeln(j,':(',b[j,1],',',b[j,2],')');
writeln(i,':(',x,',',y,')');
halt;
end;
if a[x-1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x-1,y,i+1);end;
if a[x+1,y]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x+1,y,i+1);end;
if a[x,y-1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y-1,i+1);end;
if a[x,y+1]=0 then begin b[i,1]:=x;b[i,2]:=y;search(x,y+1,i+1);end;
a[x,y]:=0;
end;
begin
read(n);
for k:=1 to n do
for j:=1 to n do
read(a[k,j]);
for k:=0 to n+1 do
begin
a[k,0]:=-1;
a[k,n+1]:=-1;
a[n+1,k]:=-1;
a[0,k]:=-1;
end;
x:=1;y:=1;
if a[x+1,y]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x+1,y,1);a[x,y]:=0;end;
if a[x,y+1]=0 then begin a[x,y]:=1;b[1,1]:=x;b[1,2]:=y;search(x,y+1,1);a[x,y]:=0;end;
end.

㈨ 回溯演算法的典型例題

八皇後問題：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。