9度OJ 教程103 广搜解决《珍惜现在，感恩生活》之内存超

九度OJ 教程103 广搜解决《珍惜现在，感恩生活》之内存超

内存超

http://ac.jobdu.com/problem.php?cid=1040&pid=102

#include<stdio.h>
#include<string.h>
#define MAXS 105
#include<queue>;
using namespace std;
typedef struct E{
	int weight;
	int rest_money;
	int nrest[102];//rest[m]表示该E状态下第m种大米剩余的数量
}E;
typedef struct MICE{
	int cost;
	int weight;
}MICE;
MICE mi[102];
queue < E > Q;
int main()
{
	int C,a,b,m,n,i,maxw;
	E temp,now,spa;
	memset(&spa,0,sizeof(E));
	scanf("%d",&C);
	while(C--)
	{
		memset(mi,0,102*sizeof(int));
		temp=now=spa;
		while(Q.empty()==false)Q.pop();
		maxw=0;
		scanf("%d %d",&n,&m);
		now.rest_money=n;
		for(i=1;i<=m;i++)scanf("%d %d %d",&mi[i].cost,&mi[i].weight,&now.nrest[i]);
		Q.push(now);
		while(Q.empty()==false)
		{
			now=Q.front();
			Q.pop();
			for(i=1;i<=m;i++)
			{
				if(now.nrest[i]&&now.rest_money>=mi[i].cost)
				{
					temp=now;
					temp.rest_money-=mi[i].cost;
					temp.nrest[i]--;
					temp.weight+=mi[i].weight;
					Q.push(temp);
					if(maxw<temp.weight)maxw=temp.weight;
				}
			}//for
		}//while
		printf("%d\n",maxw);
	}
	return 0;
}