0-1背包回溯q.cpp

0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯 0-1背包回溯

#include<iostream.h>
class Knap{
	friend int Knapsack(int p[],int w[],int c, int n);
public:
	int MAX;
    int x[4];
private:
	int c;          //背包容量
	int n;          //物品数
	int w[4];       //物品重量数组
	int p[4];       //物品价值数组
	int cw;        //当前重量
	int cp;        //当前价值
	int bestp;     //当前最优值
	int Bound(int i);
	int x0[4];
	void Backtrack(int i); 
};

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;
		if(MAX<bestp)
		{
			MAX=bestp;
		    for(int i2=0;i2<4;i2++)
			x0[i2]=x[i2];
		}	

		return;
	}
	if(cw+w[i]<=c)
	{
		x[i]=1;		
		cw+=w[i];
		cp+=p[i];
		Backtrack(i+1);
		cw-=w[i];
		cp-=p[i];
	}
	
	if(Bound(i)>bestp) 
	{x[i]=0;
	Backtrack(i+1);   }
}
class Object{
	friend int Knapsack(int p[],int w[],int c, int n);
public:
	int operator<=(Object a)const
	{
		return(d>=a.d);
	}
private:
	int ID;
	float d;
};

int Knapsack(int p[],int w[],int c, int n)
{
	int W=0;
	int P=0;
	Object *Q=new Object[n];
	for(int i=0;i<n;i++)
	{
		Q[i].ID=i;
		Q[i].d=1.0*p[i]/w[i];
		P+=p[i];
		W+=w[i];
	}
	if(W<=c)return P;
	Knap K;
	for(i=0;i<n;i++)
	{
	K.p[i]=p[i];
	K.w[i]=w[i]  ;}
	for(i=0;i<n;i++)
	{
		K.p[i]=p[Q[i].ID];
		K.w[i]=w[Q[i].ID];
	}
	K.cp=0;
	K.cw=0;
	K.c=c;
	K.n=n;
	K.bestp=0;
	K.MAX=0;

	
	K.Backtrack(0);
    cout<<"最优价值 "<<K.bestp<<endl;
	cout<<"选择顺序："<<endl;
	for(int j=0;j<4;j++)
       cout<<K.x0[j]<<' ';
	return K.bestp;
		
			
			
	
}
void main()
{
	int p1[3]={45,25,25};
	int w1[3]={16,15,15};
	int	c1=30,n1=3;
	Knapsack( p1,w1, c1,n1 );
	 
}