题目：
今天是阴历七月初五，acm队员zb的生日。zb正在和C小加、never在武汉集训。他想给这两位兄弟买点什么庆祝生日，经过调查，zb发现C小加和 never都很喜欢吃西瓜，而且一吃就是一堆的那种，zb立刻下定决心买了一堆西瓜。当他准备把西瓜送给C小加和never的时候，遇到了一个难 题，never和C小加不在一块住，只能把西瓜分成两堆给他们，为了对每个人都公平，他想让两堆的重量之差最小。每个西瓜的重量已知，你能帮帮他么？
输入：
多组测试数据（<=1500）。数据以EOF结尾
第一行输入西瓜数量N (1 ≤ N ≤ 20)
第二行有N个数，W1, …, Wn (1 ≤ Wi ≤ 10000)分别代表每个西瓜的重量
输出：
输出分成两堆后的质量差
样例输入：
5
5 8 13 27 14
样例输出：
3
下面是源程序：
#include<stdio.h> #include<iostream> #include<cstdlib> #include<fstream> using namespace std; int melon[21]; int n; int mins;//不要定义为min或max,以免与库函数冲突 int total; void findmin(int i,int sum)//i为层数;sum为当前和 { if(i==n) //到i = n;时,最后一次讨论是否包含[n-1]; { int temp=abs(total - sum - sum);//当前两部分的差额 if(mins > temp) mins=temp; return; } /* 这里是一个剪枝；不用所有的都走到底部。 if(sum > total/2 )//如果当前的和已经大于一半，剪枝 { int temp=abs(total - sum - sum);//当前两部分的差额 if(mins > temp)//如果最小差额比当前的差额大 { mins = temp; } return ; } */ findmin(i+1,sum);//不算melon[i] findmin(i+1,sum+melon[i]);//算上melon[i] } int main() { int i; while(cin>>n) { total=0; mins=9999999; for(i=0;i<n;i++) { scanf("%d",&melon[i]); total+=melon[i];//西瓜总重量 }//for if(n==0) cout<<melon[0]<<endl; else { findmin(0,0); cout<<mins<<endl; } }//while return 0; }
深度优先，就是从一个点出发，一直深入下去，直到叶子节点，然后返回，在深入，直到
遍历完所有的节点，为了深刻的理解遍历的过程，可以单步跟踪一下。
单步跟踪：遇到函数按F11,进入函数;进入函数后按F10,单步走。这样就可以清楚的查看每一步。
下面就是跟从得到的树状图：
注释：输入的数据是： 2 1 2
就是从两个，分别是1和2 [0]代表第0个，[1]代表第1个。
遍历时就会把所有的情况都遍历一遍，每个元素都可能在或不在集合中。
问题2 素数环
有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。
为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。
输入：
有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束
输出：
每组第一行输出对应的Case序号，从1开始。
如果存在满足题意叙述的素数环，从小到大输出。
否则输出No Answer。
样例输入：
6
8
3
0
样例输出：
分析：
(1)如果n为奇数，那么必然有两个奇数相邻，他们的和为偶数，不是素数。
(2)一边排列一边检查，提前剪枝。
(3)递归思想：如果要求一个数组，或者是否包含某些元素，都是在main{}中调用时
令层数t=0,传递，然后在递归函数中增加t,如f(t+1);这样就深入了。
还要有判断条件一般都是t==n时，判断是不是满足某些条件，然后再返回。
当然，剪枝就是提前返回，就是t没有到n时就返回了。
下面是源代码：
#include<iostream>
#include<stdio.h>
using namespace std;
//直接通过一个数对应的索引号查看是不是素数
bool IsPrime[]={
0, 0, 1, 1, 0, 1, 0,
1, 0, 0, 0, 1, 0, 1,
0, 0, 0, 1, 0, 1, 0,
0, 0, 1, 0, 0, 0, 0,
0, 1, 0, 1, 0, 0, 0,
0, 0, 1
};//因为n<20；最大素数和为19+18=37;
void Output(int a[],int n)
{
int i;
cout<<"1";
for(i = 1 ; i < n ; i++ )
{
cout << " "<<a[i];
}
cout<<endl;
}
bool IsOk(int a[],int lastindex,int cur)//判断当前序列是不是合法
{
if(lastindex < 0) //!!!!!!!!!关键，0 号没有前驱，千万不要写成lastindex < 1
return true;
if(!IsPrime[cur+a[lastindex]]) //加入时与前一个元素的和不是素数
return false;
for(int i = 0;i <= lastindex; ++i)//判断这个数字是不是被用过了
{
if(cur == a[i])
return false;
}
return true;
}
void PrimeCircle(int a[],int n,int t)//判断是不是素数环,t为层数
{
if(n == 1)
{
cout<<"1"<<endl;
return;
}
if((n & 1) ==1 )//奇数没有素数环
return;
if(n == t)//结束条件一般都是t==n, 因为递归时用到t+1,传到下层为n=t+1;
//所以t=[n-1]是末尾
{
if(IsPrime[a[0] + a[n-1]]) //判断首尾
Output(a,n);
return;
}
for(int i = 1;i <= n; ++i) //判断1 到 n 是否满足条件
{
a[t] = i;//
if(IsOk(a, t-1, i)) //判断新加入的值是不是满足条件
PrimeCircle(a, n ,t+1);//深入
}
}
int main()
{
int n;
int cnt=0;
while(++cnt)
{
scanf("%d",&n);
if(n == 0)
{
break;
}
int ans[20]={1};
printf("Case %d:\n",cnt);
//因为要多次返回，所以不能这么判断bool flag=PrimeCircle(ans,n,1);
//一般都是从t=0层开始，这里第一个数已经定为1
if( n % 2 == 0 || n ==1 )
PrimeCircle(ans,n,1);
else
printf("No Answer\n");
}
return 0;
}
注：http://www.cnblogs.com/graphics/archive/2010/03/27/1698403.html