1.回溯算法就是一种有组织的系统最优化搜索技术，可以看作蛮力法穷举搜索的改进。回溯法常常可以避免搜索所有可能的解，所以它适用于求解组织数量较大的问题。
2.首先我们先了解一下一个基本概念“解空间树”：问题的解空间一般使用解空间树的方式来组织，树的根节点位于第1层，表示搜索的初始状态，依次向下排列。
3.解空间树的动态搜索：在搜索至树中任一节点时，先判断该节点对应的部分是否是满足约束条件，或者是否超出目标函数的界，也就是判断该节点是否包含问题的最优解。如果肯定不包含，则跳过对该节点为根的子树的搜索，即所谓的剪枝；否则，进入该节点为根的子树，继续按照深度优先策略搜索。（这也是为什么回溯可以避免搜索所有的解）
4.在搜索过程中，通常采用两种策略避免无效搜索：
用约束条件剪除得不到的可行解的子树用目标函数剪取得不到的最优解的子树 （这两种方式统称为：剪枝函数）5.在用回溯法求解问题时，常常遇到两种典型的解空间树：
子集树：但所有的问题是从n个元素的集合中找出满足某种性质的子集时，相应的解空间树成为子集树排列树：当所给出问题是确定n个元素满足某种性质的排列时，相应的解空间称为排列树。6.回溯法的一般步骤：
设置初始化的方案（给变量赋初始值，读入已知数据等）变换方式去试探，若全部试完侧转（7）判断此法是否成功（通过约束函数），不成功则转（2）试探成功则前进一步再试探正确方案还是未找到则转（2）以找到一种方案则记录并打印退回一步（回溯），若未退到头则转（2）已退到头则结束或打印无解7.回溯法的优点在于其结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。
给定一组整数，从里面挑选出一组整数，让选择的整数和与剩余的整数和的差最小。
int arr[] = { 12,6,7,11,16,3,9}; //给出的数组 const int length = sizeof(arr) / sizeof(arr[0]); int x[length] = { 0 }; // 子集树辅助数组 记录节点走向左孩子还是右孩子，代表i节点被选择&未被选择 int bestx[length] = { 0 }; // 记录最优解 unsigned int min = 0xFFFFFFFF; // 记录最小的差值 int sum1 = 0; // 记录所选子集数字的总和 int sum2 = 0; // 记录未选择数字的和 void fun1(int i) { if (i == length) { int result = abs(sum1 - sum2); if (result < min) { min = result; for (int k = 0; k < length; k++) { bestx[k] = x[k]; } } } else { sum2 -= arr[i]; //更新未选择的总和 sum1 += arr[i]; //更新选择的总和 x[i] = 1; fun1(i + 1); sum2 += arr[i]; //更新没有选择的总和 sum1 -= arr[i]; //更新选择的总和 x[i] = 0; fun1(i + 1); } } int main() { //未选择的数字和 for (int v : arr) { sum2 += v; } fun1(0); for (int i = 0; i < length; ++i) { if (bestx[i] == 1) { cout << arr[i] << " "; } } cout << endl; cout << "min:" << min; return 0; }那么我们如何提高子集树的效率呢？
我们要想提高子集树的效率就必须对子集树进行剪枝操作，也就是避免无效的搜索。
接下来我们对上面的题进行改变：给定2N个整数，从里面挑选出N个整数，让选择的整数和与剩余的整数和的差最小。
int arr[] = { 12,6,7,11,16,3,8,4 }; const int length = sizeof(arr) / sizeof(arr[0]); vector<int> x; // 记录子集中选择的元素 vector<int> bestx; // 记录最优解 int sum = 0; // 记录子集中所选数字的和 int r = 0; // 记录未选择数字的和 unsigned int min = 0xFFFFFFFF; // 记录最小差值 int leftcnt = length; // 记录未处理的数字的个数 // int cnt = 0; // 记录遍历的子集的个数，用于测试 void func(int i) { if (i == length) { // cnt++; // 得到子集树的一个解，对应一个叶子节点 int result = abs(sum - r); if (result < min) { min = result; bestx = x; } } else { leftcnt--; // 表示处理i节点，表示剩余的未处理的元素的个数 if (x.size() < length / 2) // 剪左树枝，提高算法效率。选择数字的前提：还未选择够n个整数 { sum += arr[i]; r -= arr[i]; x.push_back(arr[i]); func(i + 1); // 遍历i的左孩子，表示选择i号位元素 sum -= arr[i]; r += arr[i]; x.pop_back(); } // 这里右树枝可不可以剪枝呢？ 已选择的数字的个数 + 未来能选择的所有的数字的个数(i+1,i+2....n) >= n个元素 if (x.size() + leftcnt >= length / 2) { func(i + 1); // 遍历i的右孩子，表示不选择i号位元素 } // 当前i节点已处理完成，回溯到其父节点了 leftcnt++; } } int main() { for (int v : arr) { r += v; } func(0); for (int v : bestx) { cout << v << " "; } cout << endl; cout << "min:" << min << endl; //cout << "cnt:" << cnt << endl; return 0; }有一组整数，请挑选出一组数字，让他们的和等于指定的值，存在解打印，不存在打印
int arr[] = { 4,8,12,16,7,9,3 }; //给出的数组 const int length = sizeof(arr) / sizeof(arr[0]); int add = 18; //要等于的和 vector<int> x; // 子集树辅助数组 记录节点走向左孩子还是右孩子，代表i节点被选择&未被选择 int sum1 = 0; // 记录所选子集数字的总和 int r = 0; // 记录未处理数字的和 int cnt = 0; void funn(int n) { if (n == length) { cnt++; if (sum1 != add) { return; } for (int v : x) { cout << v << " "; } cout << endl; } else { r -= arr[n]; // 处理当前i节点 if (sum1+arr[n] <= add) // 剪左树枝 已选择的数字的和+即将要选择的数字 { sum1 += arr[n]; x.push_back(arr[n]); funn(n + 1); x.pop_back(); sum1 -= arr[n]; } if (sum1 + r >= add) // 剪右树枝 已选择的数字的和+剩余的可以被选择的数字的和 { funn(n + 1); } r += arr[n]; } } int main() { for (int v : arr) { r += v; } funn(0); cout << cnt; return 0; }用穷举法进行多叉树的选择
int arr[] = { 4,8,12,16,7,9,3 }; const int length = sizeof(arr) / sizeof(arr[0]); int number = 18; vector<int> vec; // 存放选择的数字 void func(int i, int number) { if (number == 0) { for (int v : vec) { cout << v << " "; } cout << endl; } else { // 以当前节点开始，把剩余元素的孩子节点生成 for (int k = i; k < length; ++k) { if (number >= arr[k]) // 剩余的元素小于number（待组成的元素值） { vec.push_back(arr[k]); // 不允许重复选择元素 func(k + 1, number - arr[k]); // 遍历孩子节点，arr[k]的孩子节点 vec.pop_back(); } } } } int main() { func(0, number); return 0; }有一组物品，其重量分别是:w1,w2,...wn，其价值分别是v1,v2,...,vn，现在有一个背包，其容量是C， 问怎么把物品装入背包，能够使背包的价值最大化？
int w[] = { 12,5,8,9,6 }; // 物品的重量 int v[] = { 9,2,4,7,8 }; // 物品的价值 int ccc = 20; //背包的容量 const int length = sizeof(w) / sizeof(w[0]); vector<int> x; // 选择的物品 vector<int> bestx; // 记录最优选择的物品 int sum = 0; //选择的重量 int aaa = 0; //选择的重量价值 int best = 0; //最重的重量 int r = 0; // 未处理物品的总价值 void fun(int i) { if (i == length) { if (best < aaa) { best = aaa; bestx = x; } } else { r -= v[i]; if (sum+w[i] <= ccc) // 已选择物品的重量 + 即将选择的第i号物品的重量 { sum += w[i]; aaa += v[i]; x.push_back(w[i]); fun(i + 1); aaa -= v[i]; sum -= w[i]; x.pop_back(); } if (r + aaa > best) //aaa + [i+1,i+2.....n]总价值 > bestv { fun(i + 1); } r += v[i]; } } int main() { for (int val : v) { r += val; } fun(0); for (int w : bestx) { cout << w << " "; } cout << endl; cout << "best:" << best << endl; return 0; }如何求一个序列的全排列？？？
void swap(int arr[], int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } void func(int arr[], int i, int length) { if (i == length) { for (int j = 0; j < length; ++j) { cout << arr[j]<<" "; } cout << endl; } else { // 生成i节点的所有孩子节点 for (int k = i; k < length; ++k) { swap(arr, i, k); func(arr, i + 1, length); swap(arr, i, k); // 一定要再交换回来 } } } int main() { int arr[] = { 1,2,3,4 }; int length = sizeof(arr) / sizeof(arr[0]); func(arr, 0, length); return 0; }以国际象棋为背景的问题：有八个皇后（可以当成八个棋子），如何在 8*8 的棋盘中放置八个皇后，使得任意两个皇后都不在同一条横线、纵线或者斜线上。
int cnt = 0; // 统计8皇后的排列次数 void swap(int arr[], int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } bool judge(int ar[], int i) // i表示当前放置皇后棋子的位置 { for (int j = 0; j < i; ++j) { if (i == j || ar[i] == ar[j] || abs(i - j) == abs(ar[i] - ar[j])) { return false; } } return true; } void func(int ar[], int i, int length) { if (i == length) { cnt++; for (int j = 0; j < length; ++j) { cout << ar[j] << " "; } cout << endl; } else { for (int k = i; k < length; ++k) { swap(ar, i, k); if(judge(ar, i)) // 判断第i个位置的元素，是否满足8皇后的条件 0 - i-1 func(ar, i + 1, length); // 生成孩子节点，也就是说会生成一系列的排列方式 swap(ar, i, k); } } } int main() { // 把ar数组的下标当作行，下标对应的元素的值当作列 int ar[] = { 1,2,3,4,5,6,7,8 }; int n = 8; func(ar, 0, n); cout << "cnt:" << cnt << endl; return 0; }
