zyzz.cpp

用回溯法求解0—1背包问题

// ZYZZ.cpp: implementation of the CZYZZ class.
//
//////////////////////////////////////////////////////////////////////
//利用回溯法求解装载问题
//何茂顺 2008.4.8
#include "stdafx.h"
#include "hmssuanfa.h"
#include "ZYZZ.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

void Loading::Backtrace(int i)
{//搜索第i层节点
	if(i > n)
	{ 
		if (cw > bestw)
		{
			for (int j =1; j <= n; j++)
				bestx[j] = x[j];
			bestw = cw;
		}
		return;
	}
	//搜索子树
	r -= w[i];
	//搜索左子数
	if(cw + w[i] <= c)
	{
		x[i] = 1;
		cw += w[i];
		Backtrace(i+1);
		cw -= w[i];
	}
	//搜索右子数
	if(cw + r > bestw)
	{
		x[i] = 0;
		Backtrace(i+1);
	}
	r += w[i];
}
int MaxLoading(int w[],int c,int n,int bestx[])
{//返回最优载重量
	Loading X;
	X.x = new int[n+1];
	X.w= w;
	X.c = c;
	X.n = n;
	X.bestx = bestx;
	X.bestw = 0;
	X.cw = 0;
	//初始化r
	X.r = 0;
	for(int i = 1;i <=n; i++)
		X.r += w[i];
	X.Backtrace(1);
	delete []X.x;
	return X.bestw;
	
	}