test.cpp

实现背包的最有装载

#include<iostream>
using namespace std;

int c,n;					//c为背包容量,n为物品数量
int cw=0,cv=0,bestv=0;		//cw为已装容量，cv为已装价值,bestv最优价值
int *w,*v,*x,*bestx;


bool Check(int i,int cw)	//检查约束
{
    if(cw+x[i]*w[i]>c)
		return false;
	return true;
}

void Knapsack(int i,int cw,int cv)
{
   if(i>n)
   {     
	  if(bestv<cv)	//判断当前的解是否更优价值，如果是则替换为最优价值
	  {
		 bestv=cv;
		 for(int k=1;k<=n;k++)//把最优解替换为当前的最优解
			 bestx[k]=x[k];
	  }
   }//end for
   else
   {
      for(int j=1;j>=0;j--)
	  {
		  x[i]=j;		  
		  if(Check(i,cw))
		  {
            cw+=w[i]*x[i];
		    cv+=v[i]*x[i];
			Knapsack(i+1,cw,cv);
			cw-=w[i]*x[i];
			cv-=v[i]*x[i];
		  }//end if of for		  
	  }//end for of else	  
   }//end else   
}


void main()
{
	
	int i;
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
		//从文件输入物品数量n和背包容量c
	cin>>n>>c;	
	w=new int[n+1];
	v=new int[n+1];
	x=new int[n+1];
	bestx=new int[n+1];
		//从文件输入物品重量w[i]和价值v[i]
	for(i=1;i<=n;i++)
		cin>>w[i];
	for(i=1;i<=n;i++)
		cin>>v[i];

	Knapsack(1,cw,cv);

	cout<<bestv<<endl;
    for(i=1;i<=n;i++)
		cout<<bestx[i]<<"\t";	
   cout<<endl;
	
	delete(w);
    delete(v);
    delete(x);
	delete(bestx);
	fclose(stdin);
	fclose(stdout);
	
}