回溯 利用的 是dfs  深度搜索  和树状图  结合 解决问题 

 回溯 的核心代码 模板

void traceback(int x){	if()	{		操作 		return;	}	else	{		for(i=下界;i

经典的 回溯  就是n 皇后问题 

今天 又学习了用回溯解决01 背包问题 以及用二进制碎片化解决 01代码

01背包 最优解问题 

/*01 背包 回溯解决算法   dfs 深度搜索  */ #include
    
     #define n 3 int maxvalue=0;int c=30;int va[3]={45,25,25};int we[3]={16,15,15};int tempva=0,tempwe=0;void traceback(int x){	if(x==n)	{//		printf("%d\n",tempva);//		if(tempva>maxvalue&&tempwe<=c)//在这里判断的话 所有的情况都遍历到  算法 不优化 		if(tempva>maxvalue) 		{			maxvalue=tempva;//更新  		}		return;	}	{		traceback(x+1);//不放						if(tempwe+we[x]<=c)// 重量 小于背包总量  提前做个判断 如果加上 背包超出直接 下面的不进行搜索 		{			tempwe+=we[x];			tempva+=va[x];			traceback(x+1);			tempwe-=we[x];//变化回来  			tempva-=va[x];			} 	}}int main(){	traceback(0);//	printf("%d\n",maxvalue);	return 0;}
    

如果是运用 二进制碎片化代码进行的话   原理就是暴力解决 将所有的情况 用01  表示  

//  01 背包 暴力解决  01代码 型   #include
    
     #include
     
      int va[3]={45,25,25};int we[3]={16,15,15};int c=30;int maxvalue=0;int n=3;int main(){	int i,j,num;	int tempva,tempwe,tempnum;	for(num=0;num
      
       maxvalue&&tempwe<=c)//如果 价值最大 并且 容量小于总		{			maxvalue=tempva;		 } 			}	printf("%d\n",maxvalue);	return 0;}