浅析回溯算法

?

1、回溯法的基本思想

/** * 背包问题 * **/#include<stdio.h>#define CAPACITY 30 //背包总容量#define MAX_NUM 10 //最多输入的物品数量int weight[MAX_NUM];//物品重量int cost[MAX_NUM]; //物品价值int remark[MAX_NUM]={0};//记录各个物品的个数int allValue=0;int m; //输入的物品个数//初始化背包信息void init(){int i;printf("输入物品数量：\n");scanf("%d",&m);printf("依次输入物品：\n重量 价值\n");for(i=0;i<m;i++)scanf("%d%d",&weight[i],&cost[i]);}//判断是否超重int overWeight(int n){ int i;int sum=0;for(i=0;i<=n;i++)sum+=remark[i]*weight[i];return sum>CAPACITY;}//回溯搜索解void search(int n){int i,j,temp;int sum=0;if(n==m)return;//选择物品for(i=0;i<2;i++){temp=remark[n];remark[n]=i;if(!overWeight(n)){//减枝sum=0; for(j=0;j<=n;j++)sum+=cost[j]*remark[j];if(sum>allValue)allValue=sum;search(n+1);//注意回溯时返回上一个值remark[n]=temp;}}}void main(){int i;init();search(0);printf("总价值：%-4d\n",allValue);printf("物品个数：\n");for(i=0;i<m;i++)printf("%-4d",remark[i]);printf("\n");}

?

?

?

/** *  农夫过河问题 **/#include<stdio.h>#define MAX_STEP  50//记录农夫、狼、羊、白菜是否过河。为0表示没过河，为1表示已经过河int sign[4]={0};//记录各个状态int remark[MAX_STEP][4]={0,0,0,0};int step=1;//指示下一个要走的方向，0表示回来，1表示过河int dir=1;//判断当前状态是否安全int safe(){int i;//狼羊单独呆一起    if(sign[1]==sign[2] && sign[2]!=sign[0])     return 0;//羊白菜单独呆一起    if(sign[3]==sign[2] && sign[2]!=sign[0]) return 0;for(i=0;i<step;i++)//这个状态出现过       if(remark[i][0]==sign[0] && remark[i][1]==sign[1]   && remark[i][2]==sign[2] && remark[i][3]==sign[3]) return 0;return 1;}//过河void cross(){int i;//全部过河    if(remark[step-1][0] && remark[step-1][1]&& remark[step-1][2] && remark[step-1][3]){for(i=0;i<step-1;i++){if(remark[i+1][0]-remark[i][0]>0)printf("第%d步：农夫过河  ",i+1);else if(remark[i+1][0]-remark[i][0]<0)printf("第%d步：农夫回来  ",i+1);if(remark[i+1][1]-remark[i][1]>0)printf("狼过河  ",i+1);else if(remark[i+1][1]-remark[i][1]<0)printf("狼回来  ",i+1);if(remark[i+1][2]-remark[i][2]>0)printf("羊过河  ",i+1);else if(remark[i+1][2]-remark[i][2]<0)printf("羊回来  ",i+1);if(remark[i+1][3]-remark[i][3]>0)printf("白菜过河  ",i+1);else if(remark[i+1][3]-remark[i][3]<0)printf("白菜回来  ",i+1);printf("\n");}printf("finish\n");return ;} //狼单独过河或者选择一个一起过河.i=0表示农夫单独过河for(i=0;i<4;i++){if(sign[i]==dir)continue;sign[0]=dir;        if(i)sign[i]=dir;if(safe()){remark[step][0]=sign[0];remark[step][1]=sign[1];remark[step][2]=sign[2];remark[step++][3]=sign[3];            dir=dir==0;//注意改变方向cross();//递归//注意回溯时返回上一个状态变量的值step--;dir=dir==0;}sign[0]=sign[0]==0;if(i)sign[i]=sign[i]==0;}}void main(){cross();}

?

?

?