backtrack.cpp

回溯算法的应用

#include<stdlib.h>
#include<stdio.h>
#include<iostream.h>

typedef int Status;
typedef int Type;

int n=0;	//集装箱数
Type *x=(Type*)malloc((50)*sizeof(Type));//当前解
Type *bestx=(Type*)malloc((50)*sizeof(Type));//当前最优解
Type c=0,	//第一艘轮船的载重量
	cw=0,		//当前载重量
	bestw=0,	//当前最优载重量 
	r=0,
	*w=(Type*)malloc((50)*sizeof(Type));	//集装箱重量数组

int Backtrack(int i)//搜索第i层节点
{
	int j_index;
//如果到达叶结点，则判断当前的cw，如果比前面得到的最优解bestw好，则替换原最优解。
	if(i>n)
	{
		if(cw>bestw)
		{
			for(j_index=1; j_index<=n; j_index++)
				bestx[j_index]=x[j_index]; bestw=cw;
		}
		return 1;
	}

	//搜索自树
	r-=w[i];
	if(cw+w[i]<=c)//搜索左子树,如果当前剩余空间可以放下当前物品也就是， cw + w[ i ] <= c
	{
		x[i]=1;
		cw+=w[i];//把当前载重  cw += w[ i ]
		Backtrack(i+1);//递归访问其左子树，Backtrack( i + 1 )
		cw-=w[i];//访问结束，回到调用点， cw - = w[ i ]
	}

	if(cw+r>bestw)//搜索右子树
	{
		x[i]=0;
		Backtrack(i+1);
	}
	r+=w[i];
}
Type* Initiate()
{
	int index=1;

	printf("输入集装箱个数：");
	scanf("%d",&n);
	printf("输入轮船载重量：");
	scanf("%d",&c);

	while(index<=n)//数组从1号单元开始存储
	{
		printf("输入集装箱%d的重量：",index);
		scanf("%d",&w[index]);
		index++;
	}

	bestw = 0;
	cw = 0;
	r = 0;
    for(index =1;index <= n; index++)
		r += w[index]; //初始时r为全体物品的重量和
	printf("n=%d c=%d cw=%d bestw=%d r=%d\n",n,c,cw,bestw,r);

	for(index=1;index<=n;index++)
	{
		printf("w[%d]=%d    ",index,w[index]);
	}
	printf("\n");
	return w;
}
int main()
{
	int i;
	Initiate();
   //计算最优载重量
	Backtrack(1);

	for(i=1;i<=n;i++)
	{
		printf("%d    ",w[i]);
		printf("%d\n",bestx[i]);
	}
  return bestw;
}

//函数之间的参数传递：
//主函数中对全局变量赋值的操作，在其他函数中，不能保存操作结果
//解决方法：将malloc函数在主函数外调用，声明全局的空间来存储全局的变量