⑴ 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;
}
⑵ 五大基本演算法——回溯法
回溯法是一種選優搜索法（試探法）。
基本思想：將問題P的狀態空間E表示成一棵高為n的帶全有序樹T，把求解問題簡化為搜索樹T。搜索過程採用 深度優先搜索 。搜索到某一結點時判斷該結點是否包含原問題的解，如果包含則繼續往下搜索，如果不包含則向祖先回溯。
通俗來說，就是利用一個樹結構來表示解空間,然後從樹的根開始深度優先遍歷該樹，到不滿足要求的葉子結點時向上回溯繼續遍歷。
幾個結點：
擴展結點：一個正在產生子結點的結點稱為擴展結點
活結點：一個自身已生成但未全部生成子結點的結點
死結點：一個所有子結點已全部生成的結點
1、分析問題，定義問題解空間。
2、根據解空間，確定解空間結構，得 搜索樹 。
3、從根節點開始深度優先搜索解空間（利用 剪枝 避免無效搜索）。
4、遞歸搜索，直到找到所要求的的解。
1、子集樹
當問題是：從n個元素的集合S中找出滿足某種性質的子集時，用子集樹。
子集樹必然是一個二叉樹。常見問題：0/1背包問題、裝載問題。
遍歷子集樹時間復雜度：O（2^n）
2、排列樹
當問題是：確定n個元素滿足某種排列時，用排列數。常見問題：TSP旅行商問題，N皇後問題。
遍歷排列樹時間復雜度：O（n!）
通俗地講，結合Java集合的概念，選擇哪種樹其實就是看最後所得結果是放入一個List（有序）里，還是放入一個Set（無序）里。
剪枝函數能極大提高搜索效率，遍歷解空間樹時，對於不滿足條件的分支進行剪枝，因為這些分支一定不會在最後所求解中。
常見剪枝函數：
約束函數（對解加入約束條件）、限界函數（對解進行上界或下界的限定）
滿足約束函數的解才是可行解。
1、0/1背包問題
2、TSP旅行商問題
3、最優裝載問題
4、N-皇後問題
具體問題可網路詳細內容。
⑶ 9.2 回溯演算法的例子
在4 * 4的方格棋盤上放置4個皇後棋子，使得沒有兩個皇後在同一行、同一列，也不在同一條45度的斜線上， 問有多少種布局?
回溯演算法的解一般是向量，而這個題也不例外，設4維向量的<x1,x2,x3,x4>，Xi中i表示第幾個皇後，Xi表示在棋盤第i行的位置，比如其中一個解是<2,4,1,3>，如下圖
1.四皇後問題中，葉節點就是一個解。
2.四皇後每一個節點的子樹代表著下一個皇後可以放的列數，因為都是n，所以子樹都是n叉樹，故四皇後是一顆 n叉樹
3.四皇後的解至少有兩個，因為棋盤可以沿著中心線翻折
有n種物品，每種物品只有1個。第i種物品價值為vi，重量為wi，i=1，2，3...n. 問如何選擇放入背包的物品，使得總重量不超過B，而價值達到最大?
同樣，此問題的解可用一個向量來表示，該向量就代表了所有的物品，如果對應物品為1，則表示裝入背包，反之，沒有被裝入。
因此，回溯的每層可以表示為對應的物品，分支左右可以表示取或者不取（向量中表示為1或0）
總而言之，每一個節點也就是物品只有0和1兩種狀態，因此該樹一棵二叉樹，或者為 子集樹
1.選擇第一個物品，目前總重量為8，總價值為12。
2.再選擇第二個物品，總重量為14 > 13，觸發回溯。
3.不選擇第二個物品，選擇第三個商品，總重量是12，總價值為21。
4.再選擇第四個物品，總重量為15 > 13，觸發回溯。
5.不選擇第四個物品，總重量為12，總價值為21，與目前最優解價值進行比較，如果最優解價值大於21則替換目前的最優解向量和最優解價值。
1.背包問題只有在葉節點才能生成一個滿足條件的解，而之後將該解和最優解比較。
2.背包問題必須遍歷完所有的分支，才能夠獲得最終的解。
3.背包問題是一顆子集樹。
有n個城市，已知任兩個城市之間的距離， 求一條每個城市恰好經過一次的迴路，使得總長度最小 。
貨郎問題中主要的一點就是每一個點（除了第一個點）其他點必須經過且只能經過1次，這就很像數學中的排列。
因此，我們採用一個向量來表示貨郎問題的城市排列
1.貨郎問題是一顆分支不斷減少的排列數（和數學的排列類似）
2.貨郎問題也得遍歷完所有的情況，比較後得出最優解。
1.解都是用向量表示
2.搜索空間都是樹
3.搜索策略多種，有深度優先、寬度優先和跳躍式遍歷搜索樹。
⑷ (四) 回溯法(試探演算法)
約束函數和限界函數的目的是相同的，都為了剪去不必要搜索的子樹，減少問題求解所需實際生成的狀態結點數，它們統稱為剪枝函數（pruning function）。
使用剪枝函數的深度優先生成狀態空間樹中結點的求解方法稱為回溯法(backtracking)
使用剪枝函數的廣度優先生成狀態空間樹中結點的求解方法稱為分支/枝限界法(branch-and-bound)
回溯法/分支限界法 = 窮舉 + 剪枝。
回溯法是一個既帶有系統性又帶有跳躍性的搜索演算法；
這種以深度優先的方式系統地搜索問題的解得演算法稱為回溯法。其實回溯法就是對 隱式圖 的深度優先搜索演算法
回溯是窮舉方法的一個改進，它在所有可行的選擇中，系統地搜索問題的解。它假定解可以由向量形式 (x1,x2,...,xn) 來 表示，其中xi的值表示在第i次選擇所作的決策值，並以深度優先的方式遍歷向量空間,逐步確定xi 的值，直到解被找到。
若用回溯法求問題的所有解時，要回溯到根，且根結點的所有可行的子樹都要已被搜索遍才結束，來確保解的正確性。而若使用回溯法求任一個解時，只要搜索到問題的一個解就可以結束。
有許多問題，當需要找出它的解集或者要求回答什麼解是滿足某些約束條件的最佳解時，往往要使用回溯法。( 找出解空間樹中滿足約束條件的所有解 )
回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。 這種方法適用於解一些組合數較大的問題 。
（1）問題框架
（2） 遞歸的演算法框架
回溯法是對解空間的深度優先搜索，在一般情況下使用遞歸函數來實現回溯法比較簡單，其中i為搜索的深度，框架如下：
（3）非遞歸回溯框架（遞歸轉非遞歸，這里可以參考樹的遍歷，或者看上篇博客——遞歸演算法介紹）
用回溯法解題的一個顯著特徵是在搜索過程中動態產生問題的解空間。在任何時刻，演算法只保存從根結點到當前擴展結點的路徑。如果解空間樹中從根結點到葉結點的最長路徑的長度為 ，則回溯法所需的計算空間通常為 。而顯式地存儲整個解空間則需要 或 內存空間。
回溯法解題的時候常遇到兩種類型的解空間樹：
用回溯法搜索子集樹的演算法框架可描述為：
用回溯法搜索排列樹的演算法框架可描述為：
⑸ N皇後問題的回溯法求解屬於子集樹還是排列樹 詳細講一講
「八皇後」問題遞歸法求解 (Pascal語言) 八皇後問題是一個古老而著名的問題，是回溯演算法的典型例題。該問猜羨哪題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。穗碼現代教學中，把八皇後問題當成一個經典遞歸演算法例題。 演算法分析：數組a、b、c分別用來標記沖突，a數組代表列沖突，從a[0]~a[7]代表第0列到第7列，如果某列上已經有皇後，則為1，否則為0；數組b代表主對角線沖突，為b[i-j+7]，即從b[0]~b[14]，如果某條主對角線上已經有皇後，則為1，否則為0；數組c代表從對角線沖突，為c[i+j]，即從c[0]~c[14]，如果某條從對角線上已經有皇後，則為1，否則為派前0；另優化：第一個皇後在1~4格，最後*2，即為總解數 } program queens; var a:array [1..8] of integer; b,c,d:array [-7..16] of integer; t,i,j,k:integer; procere print; begin t:=t+1; write(t,': '); for k:=1 to 8 do write(a[k],' '); writeln; end; procere try(i:integer); var j:integer; begin for j:=1 to 8 do {每個皇後都有8種可能位置} if (b[j]=0) and (c[i+j]=0) and (d[i-j]=0) then {判斷位置是否沖突} begin a:=j; {擺放皇後} b[j]:=1; {宣布佔領第J行} c[i+j]:=1; {佔領兩個對角線} d[i-j]:=1; if i<8 then try(i+1) {8個皇後沒有擺完，遞歸擺放下一皇後} else print; {完成任務，列印結果} b[j]:=0; {回溯} c[i+j]:=0; d[i-j]:=0; end; end; begin fillchar(a,sizeof(a),0); {初始化數組} fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); try(1);{從第1個皇後開始放置} end. 「八皇後」問題遞歸法求解 (C語言) ＃i nclude "stdio.h" static char Queen[8][8]; static int a[8]; static int b[15]; static int c[15]; static int iQueenNum=0; //記錄總的棋盤狀態數 void qu(int i); //參數i代錶行 int main() { int iLine,iColumn; //棋盤初始化，空格為*，放置皇後的地方為@ for(iLine=0;iLine<8;iLine++) { a[iLine]=0; //列標記初始化，表示無列沖突 for(iColumn=0;iColumn<8;iColumn++) Queen[iLine][iColumn]='*'; } //主、從對角線標記初始化，表示沒有沖突 for(iLine=0;iLine<15;iLine++) b[iLine]=c[iLine]=0; qu(0); return 0; } void qu(int i) { int iColumn; for(iColumn=0;iColumn<8;iColumn++) { if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0) //如果無沖突 { Queen[iColumn]='@'; //放皇後 a[iColumn]=1; //標記，下一次該列上不能放皇後 b[i-iColumn+7]=1; //標記，下一次該主對角線上不能放皇後 c[i+iColumn]=1; //標記，下一次該從對角線上不能放皇後 if(i<7) qu(i+1); //如果行還沒有遍歷完，進入下一行 else //否則輸出 { //輸出棋盤狀態 int iLine,iColumn; printf("第%d種狀態為：\n",++iQueenNum); for(iLine=0;iLine<8;iLine++) { for(iColumn=0;iColumn2)this.width=screen.width/2" vspace=2 border=0>; } printf("\n\n"screen.width/2)this.width=screen.width/2" vspace=2 border=0>; } //如果前次的皇後放置導致後面的放置無論如何都不能滿足要求，則回溯，重置 Queen[iColumn]='*'; a[iColumn]=0; b[i-iColumn+7]=0; c[i+iColumn]=0; } } } 八皇後的c語言解法： #include #include #include int n,k,a[20],num=0; int attack(int k){ int flag=0; int i=1; while ((i<k)&&(a[k]!=a)&&(fabs(a[k]-a)!=(k-i))) i++; if (i==k) flag=1; return flag; } void place(int k) { //printf(" %d",k); int i; if (k==n+1){ num=num+1; printf("num=%d:",num); for (i=1;i<n+1;i++) printf(" %d",a); printf("\n");} else { for (i=1;i<n+1;i++){ a[k]=i; if (attack(k)==1) place(k+1); else a[k]=0; } } } main(){ scanf("%d",&n); k=1; place(k); if (k!=n+1) printf("no solution!\n"); getch(); }
⑹ 逐層剝離法,判斷演算法,觀察演算法的區別
（一）遞歸（recursion）
直接或間接地調用自身的演算法稱為遞歸演算法。用函數自身給出定義的函數稱為遞歸函數。每個遞歸函數都要有非遞歸定義的初始值。
關鍵要素：邊界條件、遞歸方程
典型案例：斐波那契、漢諾塔
（二）分治法（divide and conquer method）
將一個規模為n的問題分解為k個規模較小的子問題，這些子問題相互獨立且與原問題相同。遞歸的解這些子問題，然後將各個子問題的解合並得到原問題的解。
典型案例：二分法、歸並排序、快速排序、漢諾塔
（三）動態規劃法（dynamic programing method）
和分治法類似，都是將待求問題分解成若干個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。而動態規劃的子問題往往是重疊的，即相互不獨立，所以可以用一個表來記錄所有子問題的解，以免之後大量重復計算。
關鍵要素：最優子結構、重疊子問題、狀態轉移方程
典型案例：湊零錢、背包問題
（四）貪心法（greedy method）
貪心演算法並不從整體的最優解考慮，而是做出當前的局部最優的選擇。兩個要素是最優子結構和貪心選擇性質，貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇(即貪心選擇)來達到。
關鍵要素：最優子結構、貪心選擇性質
典型案例：無重疊區間、活動安排問題
（五）回溯法（back track method）
回溯法（探索與回溯法）是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法。
兩種典型的解空間樹：子集樹、排列樹
典型案例：N皇後問題、圖的m著色問題
（六）分支限界法（branch and bound method）
分支限界法按廣度優先策略遍歷問題的解空間，在遍歷過程種，對已經處理的每一個結點根據限界函數估算目標函數的可能值，從中選取使目標函數取得極值（極大或極小）的結點優先進行廣度優先搜索，從而不斷調整搜索方向，盡快找到問題的解。因為界限函數常常是基於問題的目標函數而確定的，所以，分支限界法適用於求解最優化問題。
常見兩種分支限界法:
（1）隊列式(FIFO)分支限界法：按照隊列先進先出（FIFO）原則選取下一個節點為擴展節點。
（2）優先隊列式分支限界法：按照優先隊列中規定的優先順序選取優先順序最高的節點成為當前擴展節點。
典型案例：0/1背包問題、單源最短路徑問題、最優裝載問題。
（七）十大經典排序演算法
菜鳥教程：https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
（八）七大查找演算法
https://www.cnblogs.com/maybe2030/p/4715035.html#_labelTop【C++】
二、演算法差異
（一）分治法和動態規劃法的區別
共同點：都是將問題分解為子問題，求解子問題，記錄子問題的解，然後合並子問題的解得到原問題的解。
不同點：動態規劃解決的問題一定是最優化問題，並且擁有重疊子問題；分治法解決的問題不一定是最優化問題，分解出的子問題是不重疊的，是相互獨立的。
（二）動態規劃法和貪心法的區別
共同點：貪心演算法和動態規劃演算法都是解決最優化問題，並要求問題具有最優子結構性質。
不同點：
動態規劃：每一步作一個選擇——依賴於子問題的解。
貪心方法：每一步作一個選擇——不依賴於子問題的解。
動態規劃方法的條件：最優子結構性質；重疊子問題性質。
可用貪心方法的條件：最優子結構性質；貪心選擇性質。
動態規劃：自底向上求解（動態規劃方法是自底向上計算各個子問題的最優解，即先計運算元問題的最優解，然後再利用子問題的最優解構造大問題的最優解，因此需要最優子結構）
貪心方法： 自頂向下求解。
（三）回溯法和分支限界法的區別
共同點：一種在問題的解空間樹上搜索問題解的演算法。
不同點：
求解目標不同，回溯法的目標是找出解空間樹滿足約束條件的所有解，而分支限界法的求解目標是盡快地找出滿足約束條件的一個解；
搜索方法不同，回溯法採用深度優先方法搜索解空間，而分支限界法一般採用廣度優先或以最小消耗優先的方式搜索解空間樹；
對擴展結點的擴展方式不同，回溯法中，如果當前的擴展結點不能夠再向縱深方向移動，則當前擴展結點就成為死結點，此時應回溯到最近一個活結點處，並使此活結點成為擴展結點。分支限界法中，每一次活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點；
存儲空間的要求不同，分支限界法的存儲空間比回溯法大得多，當內存容量有限時，回溯法成功的可能性更大。