常見的搜尋演算法可以結合列舉策略和剪枝策略：
列舉策略 剪枝策略深度優先 約束條件廣度優先 限界函式其中，列舉策略有且僅有一種（或是深度優先，或是廣度優先），剪枝策略則可以是約束條件、限界函式之一或兩者兼而有之或兩者都不考慮，然後就有了經典的列舉法（蠻力法）、回溯法、加限界的回溯法、分支限界法。
限界函式和約束條件的目標：
約束條件，是為了去掉不可行解，從而進行剪枝。
限界函式，是為了去掉非最優解（依然是可行解），從而剪枝。如果題目需要求多個可行解，那麼就不可能使用限界函式。
明確了這兩個目標，就能夠更加針對性選擇了：
Let us consider below 0/1 Knapsack problem.
下面讓我們考慮0/1揹包問題。
Given two integer arrays val[0…n-1] and wt[0…n-1] that represent values and weights associated with n items respectively. Find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to Knapsack capacity W.
給定兩個整數陣列val[0…n-1]和wt[0…n-1]，分別表示與n個項相關聯的值和權重。找出val[]的最大值子集，使該子集的權重之和小於或等於揹包容量W。
Let us explore all approaches for this problem.
讓我們探討解決這個問題的所有方法。
1. A Greedy approach is to pick the items in decreasing order of value per unit weight. The Greedy approach works only for fractional knapsack problem and may not produce correct result for 0/1 knapsack.
1 一種貪婪的方法是按每單位重量值的降序選取專案。貪心方法只適用於分數揹包問題，對於0/1揹包問題可能無法得到正確的結果。
0/1揹包問題：我們有一堆物品S={a1,a2,…,an}，每個物品ai都有一個重量wi和一個價值vi。現在有一個揹包，這個揹包的容量為W，現在要將這些物品在不超越揹包容量的情況下選擇性地放入揹包，使得揹包裡面物品的價值最大，物品不能只選取其中一部份，必須選擇全部，或不選！（放與不放到揹包裡，採用二進位制表示，1表示放入揹包，0表示不放入揹包。）
分數揹包問題：這個問題和上面的問題比較類似，唯一不同的就是該問題裡面的物品可以進行分割，便可以只選取1個物品ai的一部份。
2. We can use Dynamic Programming (DP) for 0/1 Knapsack problem. In DP, we use a 2D table of size n * W. The DP Solution doesn’t work if item weights are not integers.
2 我們可以用動態規劃（DP）求解0/1揹包問題。在DP中，我們使用大小為n * w的2D表。如果專案權重不是整數，DP解決方案就不起作用。
3. Since DP solution doesn’t alway work, a solution is to use Brute Force. With n items, there are 2^n solutions to be generated, check each to see if they satisfy the constraint, save maximum solution that satisfies constraint. This solution can be expressed as tree.
3 由於DP解決方案並不總是有效的，一個解決方案是使用暴力。對於n個專案，將生成2^n個解，檢查每個解是否滿足約束，儲存滿足約束的最大解。這個解可以表示為樹。
示例程式碼：
#include<stdio.h>#include<iostream>#include<cmath>using namespace std;#define DIM 5void possible_solution(int arr[DIM]){ for(int i=0;i<DIM;i++) // n=4,有2^4-1種解法 if(arr[i]!=1) { arr[i]=1; return; // 從遇到的第一位開始，若是0，將其變成1，然後結束迴圈，得到一種解法 } else arr[i]=0; return; // 從第一位開始，若是1，將其變成0，然後繼續迴圈，若再迴圈的時候遇到0， // 則將其變為1，結束迴圈。得到另一種解法。 }int main(){ int count=0; double weight[DIM]={2,3.14,1.98,5,3}; double value[DIM]={40,50,100,95,30}; int x[DIM]={0}; int y[DIM]={0}; double weightLimit=10; double maxv = 0; for(int j=1;j<=pow(2,DIM);j++) { possible_solution(x); count++; int i; for(i=0;i<DIM;i++) cout<<x[i]<<" "; cout<<endl; double tw = 0, tv = 0; for(i=0;i<DIM;i++) tw+=x[i]*weight[i]; for(i=0;i<DIM;i++) tv+=x[i]*value[i]; if(tw <= weightLimit && tv>maxv) { maxv=tv; for(i=0;i<DIM;i++) y[i]=x[i]; } } cout<<"共有"<<count<<"種解法."<<endl; printf("其中0-1揹包問題的最優解為：y = "); for(int i=0;i<DIM;i++) printf("%d ",y[i]); printf("\n"); printf("總價值為：%f",maxv); while(1);}/*1 0 0 0 00 1 0 0 01 1 0 0 00 0 1 0 01 0 1 0 00 1 1 0 01 1 1 0 00 0 0 1 01 0 0 1 00 1 0 1 01 1 0 1 00 0 1 1 01 0 1 1 00 1 1 1 01 1 1 1 00 0 0 0 11 0 0 0 10 1 0 0 11 1 0 0 10 0 1 0 11 0 1 0 10 1 1 0 11 1 1 0 10 0 0 1 11 0 0 1 10 1 0 1 11 1 0 1 10 0 1 1 11 0 1 1 10 1 1 1 11 1 1 1 10 0 0 0 0共有32種解法.其中0-1揹包問題的最優解為：y = 1 0 1 1 0總價值為：235.000000*/We can use Backtracking to optimize the Brute Force solution. In the tree representation, we can do DFS of tree. If we reach a point where a solution no longer is feasible, there is no need to continue exploring. In the given example, backtracking would be much more effective if we had even more items or a smaller knapsack capacity.
我們可以使用回溯來最佳化暴力解決方案。在樹表示中，我們可以做樹的DFS。如果我們到了一個解決方案不再可行的地步，就沒有必要繼續探索。在給定的例子中，如果我們有更多的物品或更小的揹包容量，回溯將更加有效。
回溯法的一般思路：
void Backtracking(){ If you are already at a solution, report success. for ( every possible choice in the current position ) { 1 Make that choice and take one step along the path. 2 Use recursion to solve the problem from the new position. 3 If the recursive call succeeds, report the success to the next higher level. 4 If not, back out of the current choice to restore the previous state. } Report failure.}01揹包屬於找最優解問題，用回溯法需要構造解的子集樹。對於每一個物品i，對於該物品只有選與不選2個決策，總共有n個物品，可以順序依次考慮每個物品，這樣就形成了一棵解空間樹：基本思想就是遍歷這棵樹，以列舉所有情況，最後進行判斷，如果重量不超過揹包容量，且價值最大的話，該方案就是最後的答案。
在搜尋狀態空間樹時，只要左子節點是一個可行結點，搜尋就進入其左子樹。對於右子樹時，先計算上界函式，以判斷是否將其減去（剪枝）。
上界函式bound()：當前價值cw+剩餘容量可容納的最大價值<=當前最優價值bestp。
為了更好地計算和運用上界函式剪枝，選擇先將物品按照其單位重量價值從大到小排序，此後就按照順序考慮各個物品。
利用回溯法試設計一個演算法求出0-1揹包問題的解，也就是求出一個解向量xi （即對n個物品放或不放的一種的方案）。
其中， (xi = 0 或１，xi = 0表示物體ｉ不放入揹包，xi ＝1表示把物體ｉ放入揹包）。
在遞迴函式Backtrack中，當i>n時，演算法搜尋至葉子結點，得到一個新的物品裝包方案。此時演算法適時更新當前的最優價值。
當i<n時，當前擴充套件結點位於排列樹的第（i-1）層，此時演算法選擇下一個要安排的物品，以深度優先方式遞迴的對相應的子樹進行搜尋，對不滿足上界約束的結點，則剪去相應的子樹。
回溯法求01揹包問題：
① 用約束函式在擴充套件結點處剪除不滿足約束的子樹；
② 用限界函式剪去得不到問題解或最優解的子樹。
#include <iostream>#include <stdio.h>using namespace std;int n; //物品數量double c; //揹包容量double v[100]; //各個物品的價值 valuedouble w[100]; //各個物品的重量 weightdouble cw = 0.0;//當前揹包重量 current weightdouble cp = 0.0;//當前揹包中物品總價值 current valuedouble bestp = 0.0; //當前最優價值best pricedouble perp[100]; //單位物品價值(排序後) per priceint order[100]; //物品編號int put[100];//設定是否裝入，為1的時候表示選擇該組資料裝入，為0的表示不選擇該組資料void knapsack() // 按單位價值排序{ int i,j; int temporder = 0; double temp = 0.0; for(i=1;i<=n;i++) perp[i]=v[i]/w[i]; //計算單位價值（單位重量的物品價值） for(i=1;i<=n-1;i++) { for(j=i+1;j<=n;j++) if(perp[i]<perp[j]) //氣泡排序perp[],order[],sortv[],sortw[] { temp = perp[i]; //冒泡對perp[]排序 perp[i]=perp[j]; perp[j]=temp; temporder=order[i]; //冒泡對order[]排序 order[i]=order[j]; order[j]=temporder; temp = v[i]; //冒泡對v[]排序 v[i]=v[j]; v[j]=temp; temp=w[i]; //冒泡對w[]排序 w[i]=w[j]; w[j]=temp; } }}void backtrack(int i) //回溯函式{ //i用來指示到達的層數（第幾步，從0開始），同時也指示當前選擇玩了幾個物品 double bound(int i); if(i>n) //遞迴結束的判定條件 { bestp = cp; return; } // 如若左子節點可行，則直接搜尋左子樹; // 對於右子樹，先計算上界函式，以判斷是否將其減去 if(cw+w[i]<=c) // 將物品i放入揹包，搜尋左子樹 { cw+=w[i]; // 同步更新當前揹包的重量 cp+=v[i]; // 同步更新當前揹包的總價值 put[i]=1; backtrack(i+1); // 深度搜索進入下一層 cw-=w[i]; // 回溯復原 cp-=v[i]; // 回溯復原 } if(bound(i+1)>bestp)// 若符合條件則搜尋右子樹 backtrack(i+1);}double bound(int i) // 計算上界函式，功能為剪枝{ // 判斷當前揹包的總價值cp＋剩餘容量可容納的最大價值<=當前最優價值 double leftw= c-cw; // 剩餘揹包容量 double b = cp; // 記錄當前揹包的總價值cp,最後求上界 //以物品單位重量價值遞減次序裝入物品 while(i<=n && w[i]<=leftw) { leftw-=w[i]; b+=v[i]; i++; } // 裝滿揹包 if(i<=n) b+=v[i]/w[i]*leftw; return b;// 返回計算出的上界 }int main(){ int i; printf("請輸入物品的數量和揹包的容量："); scanf("%d %lf",&n,&c); printf("請依次輸入%d個物品的重量:\n",n); for(i=1;i<=n;i++){ scanf("%lf",&w[i]); order[i]=i; } printf("請依次輸入%d個物品的價值:\n",n); for(i=1;i<=n;i++){ scanf("%lf",&v[i]); } knapsack(); backtrack(1); printf("最優價值為：%lf\n",bestp); printf("需要裝入的物品編號是："); for(i=1;i<=n;i++) { if(put[i]==1) printf("%d ",order[i]); } while(1); return 0;}/*51023.141.985340501009530 *//*請輸入物品的數量和揹包的容量：510請依次輸入5個物品的重量:23.141.9853請依次輸入5個物品的價值:40501009530最優價值為：235.000000需要裝入的物品編號是：3 1 4*/The backtracking based solution works better than brute force by ignoring infeasible solutions. We can do better (than backtracking) if we know a bound on best possible solution subtree rooted with every node. If the best in subtree is worse than current best, we can simply ignore this node and its subtrees. So we compute bound (best solution) for every node and compare the bound with current best solution before exploring the node.
基於回溯的解決方案透過忽略不可行的解決方案比暴力解決方案效果更好。如果我們知道每個節點根上的最佳可能解子樹的界，我們可以做得更好（比回溯）。如果子樹中的最佳值比當前最佳值差，我們可以忽略此節點及其子樹。因此，我們計算每個節點的邊界（最佳解），並在探索節點之前將邊界與當前最佳解進行比較。
Example bounds used in below diagram are, A down can give $315, B down can $275, C down can $225, D down can $125 and E down can $30.
下圖中使用的示例邊界是，A向下可以給出315美元，B向下可以給出275美元，C向下可以給出225美元，D向下可以給出125美元，E向下可以給出30美元。
Branch and bound is very useful technique for searching a solution but in worst case, we need to fully calculate the entire tree. At best, we only need to fully calculate one path through the tree and prune the rest of it.
分枝定界是搜尋解的一種非常有用的技術，但在最壞的情況下，我們需要完全計算整個樹。充其量，我們只需要完全計算透過樹的一條路徑，然後修剪其餘的路徑。
Branch and bound is an algorithm design paradigm which is generally used for solving combinatorial optimization problems. These problems typically exponential in terms of time complexity and may require exploring all possible permutations in worst case. Branch and Bound solve these problems relatively quickly.
分枝定界是一種常用於求解組合最佳化問題的演算法設計正規化。這些問題的時間複雜度通常是指數級的，在最壞的情況下可能需要研究所有可能的排列。分支定界可以較快地解決這些問題。
示例程式碼：
/*測試資料：5102 3.14 1.98 5 340 50 100 95 30packageWeight = 10n = 5weight = {2,2,6,5,4}value = {6,3,5,4,6}*/#include <iostream>#include <queue>using namespace std;class AnswerWay{public: AnswerWay *parent; // 指向父親結點 bool way; // 是左邊進入還是右邊進入};class Node{public: operator double() const // 比較優先順序 { return priority; } double priority; // 結點的優先順序 double nowValue; // 當前結點的價值 double nowWeight; // 當前重量 int level; // 當前的層數 AnswerWay *answer; // 結點路徑};class Package{public: void getMaxValue(); // 獲取最大值private: void addPriorityQueue(double, double, double, int, bool);// 加入優先佇列 double bound(int); // 求出價值上界 double maxValue(); // 揹包的可容納最大價值 void sort(); // 對物品單位價值進行排序 void init(); // 對package的各個屬性進行初始化 void destructor(); // 清理new產生的空間 void getError() // 測試錯誤,可刪除 { for(int i = 0; i <= n; i++) cout<<"value = "<<value[i]<<" weight = "<<weight[i]<<endl; }private: double packageWeight; // 揹包的重量 int n; // 物品的總數 double* weight; // 每個物品的重量 double* value; // 每個物品的價值 double nowWeight; // 揹包的當前重量 double nowValue; // 揹包的當前價值 int level; // 當前層次 priority_queue<Node> prQueue; // 優先佇列 AnswerWay *answer; // 結點路徑 bool* bestWay; // 最優解};void Package::destructor() // 清除new產生的空間{ delete[] weight; delete[] value; delete[] bestWay;}void Package::getMaxValue() // 獲取到揹包的最優值{ init(); sort(); cout<<"揹包可容納的最優值為: "<<maxValue()<<endl; // 獲取最優值 cout<<"最優解為: "<<endl; // 獲取最優解 for(int i = 1; i <= n; i++) if(bestWay[i]) cout<<"weight = "<<weight[i]<<" value = "<<value[i]<<endl; destructor();}double Package::maxValue() // 計算揹包的最優值{ double bestValue = 0; // 當前最優值 double priority = bound(1); // 價值上界，也就是將要加入優先佇列中的優先順序 Node node = Node(); // 結點應放在外面定義 while(level != (n+1)) { if((nowWeight+weight[level]) <= packageWeight) { if((nowValue+value[level]) > bestValue) bestValue = nowValue + value[level]; // 左兒子的價值上界是包括了該結點的 addPriorityQueue(priority, nowValue+value[level], nowWeight+weight[level], level+1, true); } // level+1是因為這一層的物品沒有放進揹包，對右兒子來說，剩餘價值就是從level+1開始 priority = bound(level+1); if(priority >= bestValue) addPriorityQueue(priority, nowValue, nowWeight, level+1, false); node = prQueue.top(); // 從優先佇列中獲取到優先順序最高的元素 prQueue.pop(); // 更新當前各個屬性值 nowWeight = node.nowWeight; nowValue = node.nowValue; priority = node.priority; answer = node.answer; level = node.level; } for(int i=n; i>0; i--) { bestWay[i] = answer->way; answer = answer->parent; } return bestValue;}void Package::sort() // 對物品單位價值進行排序{ double tempUnitValue; // 臨時單位價值 double tempValue; // 臨時價值 double tempWeight; // 臨時重量 double *unitValue = new double[n+1]; // 物品的單位價值 unitValue[0] = 0; for(int i = 1; i <= n; i++) unitValue[i] = double(value[i])/double(weight[i]); for(i = 1; i <= n; i++) { for(int j = i; j <= n; j++) { if(unitValue[i] < unitValue[j]) { tempUnitValue = unitValue[i]; unitValue[i] = unitValue[j]; unitValue[j] = tempUnitValue; tempValue = value[i]; value[i] = value[j]; value[j] = tempValue; tempWeight = weight[i]; weight[i] = weight[j]; weight[j] = tempWeight; } } } delete[] unitValue;}void Package::init() // 對package的各個屬性進行初始化{ cout<<"請輸入有多少個物品: "<<endl; cin>>n; cout<<"請輸入揹包的容量: "<<endl; cin>>packageWeight; weight = new double[n+1]; weight[0] = 0; cout<<"請輸入各個物品的重量: "<<endl; for(int i = 1; i <= n; i++) cin>>weight[i]; value = new double[n+1]; value[0] = 0; cout<<"請輸入各個物品的價值: "<<endl; for(i = 1; i <= n; i++) cin>>value[i]; nowValue = 0; nowWeight = 0; level = 1; answer = 0; bestWay = new bool[n+1]; for(i = 0; i <= n; i++) bestWay[i] = false;}/*加入優先佇列*/void Package::addPriorityQueue(double priority, double nowValue, double nowWeight, int level, bool ch){ AnswerWay *answerTemp = new AnswerWay; answerTemp->parent = answer; answerTemp->way = ch; Node node = Node(); node.priority = priority; node.nowValue = nowValue; node.nowWeight = nowWeight; node.level = level; node.answer = answerTemp; prQueue.push(node);}/*求價值上界（從根節點的價值到當前結點的價值再加上剩餘價值）函式，必須先對物品的單位價值從大到小排序*/double Package::bound(int tempLevel){ double leftPackageWeight = packageWeight - nowWeight; double priority = nowValue; while(tempLevel <= n && weight[tempLevel] <= leftPackageWeight) { leftPackageWeight -= weight[tempLevel]; priority += value[tempLevel]; tempLevel++; } if(tempLevel <= n) priority += (value[tempLevel]*0.1)/(weight[tempLevel]*0.1)*leftPackageWeight; return priority;}int main(){ Package package = Package(); package.getMaxValue(); system("pause"); return 0;}/*請輸入有多少個物品:5請輸入揹包的容量:10請輸入各個物品的重量:2 3.14 1.98 5 3請輸入各個物品的價值:40 50 100 95 30揹包可容納的最優值為: 235最優解為:weight = 1.98 value = 100weight = 2 value = 40weight = 5 value = 95*/-End-