0-1背包回溯法.cpp

算法设计与分析 第五章王晓东版的 回溯法的0-1背包问题

#include<iostream>

 using namespace std;
 
 
class Knap
{
friend int Knapsack(int p[],int w[],int c,int n );
 
public:
	void print()
	{
		cout<<"0-1背包问题的最优解为:"<<endl;
	 for(int m=1;m<=n;m++)
   {
    cout<<bestx[m]<<" ";
   }
   cout<<endl;
   cout<<"背包问题结束！"<<endl;
	};
	void output (){cout<<"最优价值为:"<<endl;}
private:
  int Bound(int i);
  void Backtrack(int i);
 
  int c;//背包容量
  int n; //物品数
  int *w;//物品重量数组
  int *p;//物品价值数组
  int cw;//当前重量
  int cp;//当前价值
  int bestp;//当前最优值
  int *bestx;//当前最优解
  int *x;//当前解
 
};
 
 
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)
{ cout<<"执行回溯的次数"<<i<<endl;
  if(i>n)
  { cout<<"第"<<i<<"次回溯到达根节点"<<endl;
  if(bestp<cp)
	{   
    	for(int j=1;j<=n;j++)
	    	 bestx[j]=x[j];
	    bestp=cp;
		cout<<"第"<<i<<"次得到的当前最优价值是"<<bestp<<endl;
        	cout<<"输出当前最优解的路径:"<<endl;
	 for(int m=1;m<=n;m++)
   {
    cout<<bestx[m]<<" ";
   }
  }
	return;
  }
  
  if(cw+w[i]<=c) //搜索左子树
  {  cout<<"对当前第"<<i<<"层左子树搜索"<<endl;           
      x[i]=1;
	  cw+=w[i];
	  cp+=p[i];
	  Backtrack(i+1);
	  cw-=w[i];
	  cp-=p[i];
  }
	  if(Bound(i+1)>bestp)//搜索右子树
	  {   cout<<"因为当前第"<<i+1<<"层的界限函数"<<Bound(i+1)<<"大于"<<"当前最优解"<<bestp<<endl;
		  cout<<"对当前第"<<i<<"层右子树搜索"<<endl; 
	      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)
{
 //为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=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);
    K.print();
    delete [] Q;
	delete [] K.w;
	delete [] K.p;
	K.output();
	return K.bestp;

}
 
void main()
{
	int *p;
	int *w;
    int c=0;
	int n=0;
	int i=0;
 
	cout<<"请输入物品的个数："<<endl;
    cin>>n;
	p=new int[n+1];
	w=new int[n+1];
	p[0]=0;
	w[0]=0;
 
	cout<<"请输入物品的价值："<<endl;
	for(i=1;i<=n;i++)
		cin>>p[i];
 
	cout<<"请输入个物品的重量："<<endl;
	for(i=1;i<=n;i++)
		cin>>w[i];
 
	cout<<"请输入背包容量："<<endl;
	cin>>c;
 
	cout<<Knapsack(p,w,c,n)<<endl;
    
}