2602.cpp

HDOJ2501-2681acm解题报告

//递归求法   这个答案正确，但是超时!!!
#include <stdio.h> 
#define N 100 //物品总种数不是常量上线
int n;//物品总种数 
double limitW;//限制的总重量 
double totV;//全部物品的总价值 
double maxv;//解的总价值 
int option[N];//解的选择 
int cop[N];//当前解的选择 
struct {double weight; double value; }a[N]; //物品结构 
//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值 
void find(int i,double tw,double tv) 
{ 
	int k; 
	//物品i包含在当前方案的可能性 
	if(tw+a[i].weight <= limitW) 
	{ 
		cop[i]=1; 
		if(i<n-1)
			find(i+1,tw+a[i].weight,tv); 
		else 
		{ 
			for(k=0;k<n;++k) 
				option[k]=cop[k]; 
			maxv=tv; 
		} 
	} 
	cop[i]=0; 
	//物品i不包含在当前方案的可能性 
	if(tv-a[i].value>maxv) 
	{ 
		if(i<n-1)
			find(i+1,tw,tv-a[i].value); 
		else 
		{ 
			for(k=0;k<n;++k) 
				option[k]=cop[k]; 
			maxv=tv-a[i].value; 
		} 
	} 
} 
int main() 
{ 
	int k,t,m; 
	double w,v; 
	while(scanf("%d",&t) != EOF)//case数目
	{
		while(t--)
		{
			scanf("%d %lf",&n,&limitW);//物品数目和总容量
			for(totV=0.0,k=0;k<n;++k) //价值
			{ 
				scanf("%lf",&v); 
				a[k].value = v; 
				totV += v; 
			}
			for(k=0;k<n;++k) //重量
			{ 
				scanf("%lf",&w); 
				a[k].weight = w;
			}
			maxv=0.0; 
			for(k=0;k<n;++k)	cop[k]=0; 
			find(0,0.0,totV); 
			//for(k=0;k<n;++k) 
			//	if(option[k])printf("%4d",k+1); 
			//printf("%2f\n",maxv); 
			printf("%.0f\n",maxv); 
		}
	}
}