回溯1.cpp

来自「在学习计算算法分析与设计时编写的几个算法代码」· C++ 代码 · 共 56 行

#include"stdio.h"
int w[]={10,40,40};
int c=50;
int n=2;
int bestw=0;
int cw=0;
int r=90;
int x[3]={0};
int m;
int bestx[4]={0};
void backtrack(int i)
 {// 搜索第i层结点
	//return 123;
	if (i>n)// 到达叶结点
	{
      if(cw>bestw)//更新最优解bestx,bestw;return;
	  {
		  for(int j=0;j<=n;j++)
			  bestx[j]=x[j];
		  bestw=cw;
		  

	  
	 
		  }return ;
	  
	 
	}
		  
      r -= w[i];
      if (cw+w[i]<= c) {// 搜索左子树
         x[i]=1;
         cw += w[i];
         backtrack(i+1);
         cw -= w[i];      }
     if (cw+r>bestw)  // 搜索右子树
	 {
         x[i] = 0; 
         backtrack(i+1);     
         r+= w[i];
	 }
 }
main()
{
  int i;
  int k;
  backtrack(0); 
  printf("%5d\n",bestw);
  //printf("%5d\n",k);
  for(i=0;i<=n;i++)
	  printf("%5d",bestx[i]);
  printf("\n");
}