回溯法(1)

话说回溯通过剪枝可以在性能上大大高于暴力，这是很好理解的(另外，今天才知道溯读作su第四声而不是shuo)，但是比起DP来，时间复杂度还是很高的。典型的回溯解空间有子集树控件，时间复杂度为指数(如2^n)；或者排列树，时间复杂度为阶乘(n!)。回溯到思想就是走迷宫，走到死胡同了，立即退回去，走另外一条路，以此往复。
程序上，可以用递归或者非递归实现，个人认为递归实现起来简单些，只要注意将状态量适时更新就可以了。下面贴出自己的几个实现程序。

1. 递归实现0-1背包的回溯

// W 背包重量数组， V 货物价值数组，i 当前考虑货物，n 总货物数，C 背包容量
// val 当前背包装入的价值，flag 当前遍历的货物状态数组(1代表要装入背包，0表示不要)
// maxflag 能取得最大价值的货物装法，maxval 背包能装入最大价值
void backtrack_cur(int* W, int* V, int i, int n, int C, 
       int val, int* flag, int* maxflag, int& maxval)
{
 if (i == n)    // 遍历完货物一趟
 {
  if (maxval < val){      // 当前价值与已知总价值比
   maxval = val;
   copy(flag, flag+n, maxflag);   // 记下价值最大时的货物标志
  }
  return;
 }

 // 背包不装入货物i
 backtrack_cur(W, V, i+1, n, C, val, flag, maxflag, maxval);        //递归

 // 背包装入货物i，如果不能装入，则剪枝
 if (W[i] <= C) {
  val += V[i];
  C -= W[i];
  flag[i] = 1;
  backtrack_cur(W, V, i+1, n, C, val, flag, maxflag, maxval); //递归
 }
 flag[i] = 0;     // 回溯，即走回去，只是flag状态清除到以前，这样才能回溯
}

调用此函数就比较简单：backtrack_cur(W, V, 0, n, capacity, 0, flag, maxflag, maxval);

2. 非递归实现0-1背包的回溯

1) 穷举实现(其实这里非回溯)：

void enumerate(int* W, int* V, int n, int C)
{
 int space = 1 << n;   // 搜索空间，每一位代表一个货物，1代表装入背包
 int flag = space;     // 结果标记
 int weight, value, maxvalue = 0;
 for (int i = 0; i < space; ++i) {
  value = 0;  weight = 0;
  for (int j = 0; j < n; ++j) {    // 找出第j个货物是否装入背包
   weight += ((i>>j) & 1)*W[j];
   if (weight > C)
    break;
   value += ((i>>j) & 1)*V[j];
  }
  if (maxvalue < value) {        // 当前最大价值
   flag = i;
   maxvalue = value;
  }
 }
 print_rlt(flag, W, V, n, maxvalue);    // 打印结果
}

2) 迭代实现回溯：

// 非递归实现，即用迭代/循环实现回溯
int backtrack_iter(int* maxflag, int* W, int* V, int n, int C)
{
 int k = 0, val = 0, maxval = 0;    // k用来指示当前所在位置(想迷宫那样的位置)
 int rem = C;                       // 背包剩余容量
        // 访问状态，对于背包，只有1，2，3三种状态：1试图放入背包，2不放入背包，
        // 3状态访问完全，需要回溯到上一个节点。其它应用中，可以使用n+1个状态
 int* visit = new int[n];           
 int* flag = new int[n];
 memset(visit, 0, sizeof(int)*n);   // 初始化
 memset(flag, 0, sizeof(int)*n);   

 while (k >= 0) {                   // 当k<0时，回溯到初始
  for (; k < n; ++k) {       // 遍历当前路径一下的节点
   visit[k]++;        // 更新状态
   if (visit[k] == 1) {       // 第一次访问，试着装此货物到背包
    if (W[k] <= rem) {     // 能装下i货物，更新背包
     val += V[k];
     rem -= W[k];
     flag[k] = 1;
    } else {                 // 装不下，剪枝
     break;
    }
   } else if (visit[k] == 2) {      // 第二次访问，不装入背包
    if (flag[k]==1)          // 如果初次装入，则拿出
    {
     val -= V[k];
     rem += W[k];
    }
    flag[k] = 0;
   } 
                        else {     // visit[k]==3,第三次访问，状态遍历完，跳出以回溯
    visit[k]=0;  // 更新状态，下次重新访问  
    --k;
    break;
   }
  }
  if (maxval < val) {     // 此次遍历得到当前最大值？
   maxval = val;
   copy(flag, flag+n, maxflag);
  }

  if (k==n)              // 访问到叶节点？如果是，则变k，程序需要
   --k;
 }
 return maxval;
}