我觉得，回溯的算法语言很像是在做一个对人在现实中做决策情况的模拟，对于不确定对不对的决策，先试试，不行再撤销。
在不剪枝的情况下，通过选择和撤销，回溯法（或者说其实就是dfs）可以遍历决策树的全部节点，因为很适合做一些枚举全部可能解的工作。剪枝则可以快速探寻最优解问题（虽然不如分支限界）
为了能够顺利的选上和撤销，我们需要构建合适的抽象语言来描述当前的状态
作出尝试，改变相应的状态参数
递归的探索下一个分支点
在到达叶子节点或是出现某个条件不满足的情况时返回
每次返回时，恢复状态参数至尝试前的样子，以便进行可能还有的其他尝试。
把对某个元素的选与不选看作一个节点的左子树和右子树，那么对子集的枚举就是对一棵树所有叶节点的枚举。利用dfs的框架，再利用一个visit数组，就可以在遍历过程中记录当前路径的选择情况，最后在到达叶子节点的时候完成打印。
?void print(){//在到达叶子节点时打印当前分支的结果
? ? ?for(int i = 1; i <= n; i++){
? ? ? ? ?if(vis[i] == 1) cout << a[i] << " ";
? ? }
?}
?void dfs(int step){
? ? ?if(step > n) {//到达叶子节点，退出
? ? ? ? ?print();
? ? ? ? ?return;
? ? }
? ? ?vis[step] = 1;//选当前节点
? ? ?dfs(step + 1);//选了当前节点的前提下，继续遍历下一层
? ? ?vis[step] = 0;//不选
? ? ?dfs(step + 1);//不选当前节点的前提下，继续遍历下一层
?}
排列问题也可以形成自己的决策树，但不再是二叉树，而是一棵从上往下分支数量逐渐减少的树，但依旧可以使用树的遍历方法来解决此问题。同时需要一个额外的数组来记录路径。
?void dfs(int step){
? ? ?if (step > n){//叶子节点
? ? ? ? ?print();
? ? ? ? ?return;
? ? }
? ? ?for (int i = 1; i <= n; i++)
? ? {
? ? ? ? ?if (a[i]) continue; //已经用过了，跳过
? ? ? ? ?a[i] = true; ? ? ? ?//没用过则用它
? ? ? ? ?b[step] = i; ? ? ? ?//记录路径
? ? ? ? ?dfs(step + 1); ? ? //继续搜索
? ? ? ? ?a[i] = false; ? ? ? //当前路径用完退出了，还原，这样其他路径才能用
? ? }
?}
?// flag1[j]记录第j列有没有皇后
?// flag2[i + j]记录行列和为i+j有没有皇后
?// flag3[i - j + n]记录行列差为i-j+n有没有皇后
?void dfs(int step){ // step代表第几行
? ? ?if(step > n) { // 找到一个可行解后，打印
? ? ? ? ?for(int i = 1; i <= n; i++)
? ? ? ? ? ? ?cout << a[i] ?<< " ";
? ? }
? ? ?// 对每一行，尝试1 ~ n位置
? ? ?for(int y = 1 ; y <= n; y++){
? ? ? ? ?int x = step;
? ? ? ? ?//同列，同斜线，同反斜线有皇后，不能放
? ? ? ? ?if(flag1[y] || flag2[x + y] || flag3[x-y+n] ) continue;
? ? ? ? ?a[x] = y;//如果有不冲突位置，放上，并更改一系列flag
? ? ? ? ?flag1[y] = true;
? ? ? ? ?flag2[x + y] = true;
? ? ? ? ?flag3[x-y+n] = true;
? ? ? ? ?//在此状态下继续试下一行
? ? ? ? ?dfs(x + 1);
? ? ? ? ?//试完恢复状态
? ? ? ? ?flag1[y] = false;
? ? ? ? ?flag2[x + y] = false;
? ? ? ? ?flag3[x-y+n] = false;
? ? }
?}
构建了上界的概念，用于剪枝。基本遵循了选择-改状态-step+1-恢复状态的回溯标准步骤，在标准步骤执行完以后增加了不选当前节点的情况并判断是否剪枝，且因为不选，没改变状态，所以该分支只有进一步搜索，没有状态改变和恢复的过程。在叶子节点不是打印，而是判断是否更新最佳价值。
?int bound(int x){ //计算价值上界
? ? ?int rw = 0; //rp:第x个商品~第n个商品全部装入的总价值,先初始化为0
? ? ?while(x<=n) {
? ? ? ? ?rw+=w_i[x];
? ? ? ? ?x++;
? ? }
? ? ?return rw+curw; //返回当第t个商品不装时,返回前t个商品(不包括第t个)的总价值+剩余的全部商品价值
?}
?void dfs(int step){
? ? ?if(step > n){ //某个分支搜索到叶子节点 ，找到一个可行解
? ? ? ? ?if(curw > bestw){ //如果当前价值大于最优价值，更新最优解
? ? ? ? ? ? ?bestw = curw;
? ? ? ? }
? ? ? ? ?return ;
? ? }
? ? ?if(curv + v_i[step] <= v){ //判断放入第step个物品不超重，尝试放入
? ? ? ? ?x[step] = 1; //标记放入
? ? ? ? ?curv += v_i[step]; // 累加体积
? ? ? ? ?curw += w_i[step]; //累加价值
? ? ? ? ?dfs(step+1);
? ? ? ? ?curv -= v_i[step]; // 回溯，恢复当前体积
? ? ? ? ?curw -= w_i[step]; // 回溯，恢复当前价值
? ? }
? ? ?if(bound(step + 1) > bestw){ //判断不放入第step个物品，是否还有必要继续在该分支下搜索
? ? ? ? ?x[step] = 0; // 尝试不放入第i个物品
? ? ? ? ?dfs(step+1);
? ? }
?}