anpai.cpp

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

// ANPAI.cpp: implementation of the CANPAI class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "hmssuanfa.h"
#include "ANPAI.h"

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

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

int Knap::Bound(int i)
{
	//装满背包
	int cleft = c -cw;
	int b = cp;
	while (i<=n&&w[i]<=cleft)
	{
		cleft -= w[i];
		b += p[i];
		i++;
	}
    if(i<=n)
		b+=p[i]/w[i]*cleft;
    return b;
}


void Knap::Backtrack(int i)
{
	if (i>n)
	{
		bestp = cp;
		return;
	}
	if(cw + w[i] <= c)//搜索左子树
	{
		cw += w[i];
		cp += p[i];
		bestx[i] = 1;
		Backtrack(i+1);
		//	bestx[i] = 0;
        cw -= w[i];
		cp -= p[i];
	}
	if (Bound(i+1) > bestp) //搜索右子树
	{bestx[i] = 0;
	Backtrack(i+1);
	}
	
}
int Knapsack(int p[],int w[],int c,int n,int AFlag[])
{
//为Knap::Backtrack初始化
int W=0;
int P=0;
int i=1;
Object *Q=new Object[n];
for(i=1;i<=n;i++)
{
Q[i-1].ID=i;
Q[i-1].d=1.0*p[i]/w[i];
P+=p[i];
W+=w[i];
}
if(W<=c)
return P; //装入所有物品

float f;
for( i=0;i<n;i++) //依物品单位重量价值排序

for(int j=i;j<n;j++)
{
if(Q[i].d<Q[j].d)
{
f=Q[i].d;
Q[i].d=Q[j].d;
Q[j].d=f;
} 


}

Knap K;
K.p = new int[n+1];
K.w = new int[n+1];
K.x = new int[n+1];
K.bestx = new int[n+1];
K.x[0]=0;
K.bestx[0]=0;
for (i = 0; i<=n;i++)
{
	K.bestx[i] = 0.0;
}
for( i=1;i<=n;i++)
{
K.p[i]=p[Q[i-1].ID];
K.w[i]=w[Q[i-1].ID];
}
K.cp=0;
K.cw=0;
K.c=c;
K.n=n;
K.bestp=0;
//回溯搜索
K.Backtrack(1);
for (i = 1;i<=n;i++)
{
	AFlag[i] = K.bestx[i];
}
//K.print(); //打印结果
delete [] Q;
delete [] K.w;
delete [] K.p;
delete [] K.x;
delete [] K.bestx;
return K.bestp;

}