我的回溯法

回溯法(Backtracking Algorithm)有“通用的解题法”之称。用它可以系统地搜索一个问题的所有解或任一解。 
程序实现4要点：
1、表示寻找到可行解如（m==n）
2、返回
     返回只有2种情况，找到可行解 or 不满足条件（这是程序要实现的关键点）
     如何实现返回，visit[]数组，出栈和压栈
3、这些结点是怎样扩展的，多数利用循环
4、这些解是怎样保存的，题目要求可行解的个数还是最优解

看一下N皇后问题：
题目大意：在一个n*n的棋盘上放置n个皇后棋子。皇后可以向行，列，对角线攻击。求皇后互不攻击的摆法有多少种。

/*****************************EightQueen.c***************************/

#include

/*

 * NOTE: 该程序是一个解N皇后棋局问题的算法(采用递归解决)

 * 编译环境 VC++ 6

 */

/* 程序随N值的改变,从而来解决N皇后问题 */

#define N 4

int solution[N], sols;

/* 放置皇后到位置(row,col)(row,solution),若成功返回1,失败返回0 */

int place(int row)
{
    int j;
    for (j = 0; j < row; j++) /* j
    {//两个对角线
      if( row - solution[row] == j - solution[j] ||
          row + solution[row] == j + solution[j] ||
          solution[j] == solution[row] )//同一列
       return 0;
    }
    return 1;
}

/* row代表开始轮到放第 row 行了,前 row-1 行都已放好 */
void backtrack(int row)
{
    int k;//不会有N+1
    if ( N == row )
    {
        sols++;  // 解的结果加1
        /* 循环打印八皇后棋局(下标转换成从1开始) */
        for( k=0 ; k
            printf("(%d,%d) ", solution[k]+1,k+1);
        printf("\n");
    }
    else
    {
        int i;
        for( i=0 ; i
        {
            solution[row] = i;//在这一行中j循环, solution[row]的值为j,靠!!这样来扩展结点
            if( place(row) )//提前结束条件
             backtrack(row + 1);
        }
    }
}



void queens()
{
    backtrack(0);
}

int main(void)
{
    queens();
    printf("Total Solutions: %d\n", sols);
    return 0;
}

/*
(2,1) (4,2) (1,3) (3,4)
(3,1) (1,2) (4,3) (2,4)
Total Solutions: 2
Press any key to continue
*/

再看一道

编程求解，输入两个整数n和m,从数列1,2,3，……n中随意取几个数，使其和等于m。要求将所有的可能组合列出来。每个数都有两种选择，加入与不加入 实际上就是一个背包问题。

求解思路：

1.首先判断，如果n>m，则n中大于m的数不可能参与组合，此时置n = m;

2.将最大数n加入且n == m,则满足条件，输出；

3.将n分两种情况求解，（1）n没有加入，取n = n - 1; m = m;递归下去；（2）n加入，取n = n - 1l, m = m - n,递归下去

#include
#include
using namespace std;

listlist1;//相当于栈，不过出入比栈效率高
void find_factor(int sum, int n)
{
    // 递归出口
    if(n <= 0 || sum <= 0)
        return;

    // 输出找到的结果
    if(sum == n)
    {
        for(list::iterator iter = list1.begin(); iter != list1.end(); iter++)
            cout << *iter << " + ";
        cout << n << endl;//n不在栈里面的，这里的实现有点技巧
    }

    list1.push_front(n);      //还没找到，所以要进栈，典型的01背包问题,每个数都可以放或者不放
    find_factor(sum-n, n-1);   //放n，n-1个数填满sum-n
    list1.pop_front();
    find_factor(sum, n-1);     //不放n，n-1个数填满sum
}

int main()
{
    int sum, n;
    cout << "请输入你要等于多少的数值sum:" << endl;
    cin >> sum;
    cout << "请输入你要从1.....n数列中取值的n：" << endl;
    cin >> n;
    cout << "所有可能的序列，如下：" << endl;
    find_factor(sum,n);
    return 0;
}

/*
请输入你要等于多少的数值sum:
10
请输入你要从1.....n数列中取值的n：
6
所有可能的序列，如下：
6 + 4
3 + 6 + 1
4 + 5 + 1
3 + 5 + 2
2 + 3 + 4 + 1
Press any key to continue
*/

回溯法求01背包问题， 
【概要设计】

0—1背包问题是一个子集选取问题，适合于用子集树表示0—1背包问题的解空间。在搜索解空间树是，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。

#include
#include

int n=5,c=10;
int value[5]={6,3,5,4,6};
int weight[5]={2,2,6,5,4};
int cv[5]={0,0,0,0,0};
int bv[5]={0,0,0,0,0};
int cw=0;
int curv = 0 ;
int bestv =0 ;
void output()
{
   int i =0;
   for(i; i
     printf("%d ",bv[i]);
   printf("%d",bestv);
}

void trackback(int i)
{
     int j;
     //递归出口,反正一定要执行到最后
    if(i>=n)
    {
         if(bestv
        {
            for(j=0;j
                bv[j] = cv[j];
            bestv = curv;
        }
    }
    else
    {
         if(cw + weight[i]<=c)
         {
          cv[i] = 1;
          cw +=weight[i];
          curv+= value[i];
          trackback(i+1);
          //就算是符合条件，也要算上不加入的情况
          cw -=weight[i];
          curv-= value[i];
          cv[i] =0;
          trackback(i+1);
          }
          //不符合条件
          else
          {
            cv[i] =0;
            trackback(i+1);
          }

    }


}
int main(int argc, char *argv[])
{
  trackback(0);
  output();
  system("PAUSE");
  return 0;
}/*
1 1 0 0 1 15请按任意键继续. . .
*/