#include<stdio.h>
#include<string.h> 
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cmath> 
#include<map>
using namespace std;
int n,m;
double eval[4][4000000];
int  tnum[55],bou,ax[4];
struct pp
{
	int num[4],id;
	double f_value,e_value;
	double pri;
};
double dp[4000000];
int p[4000000];
pp rou[4000000];
bool cmp(pp x,pp y)
{
	return x.id<y.id;
}
pp now,heap[10000000],po,nw,query[100001],there[55];
int size;
char ch;
void heapify(int id)
{
	int l=2*id+1,r=2*id+2,ii=id;
	if(l<size&&heap[l].f_value+heap[l].e_value<heap[ii].f_value+heap[ii].e_value)
	   ii=l;
    if(r<size&&heap[r].f_value+heap[r].e_value<heap[ii].f_value+heap[ii].e_value)
       ii=r;
    if(ii!=id)
    {
    	swap(heap[ii],heap[id]);
    	heapify(ii);
    }
}
void min_heapify(int id)
{
	int ii=(id-1)/2;
	if(id&&heap[ii].f_value+heap[ii].e_value>heap[id].f_value+heap[ii].e_value)
	{
		swap(heap[ii],heap[id]);
		min_heapify(ii);
	}
}
double astar(pp x)
{
	int id,ip,i,j,s,bou=(x.num[0]+1)*(x.num[1]+1)*(x.num[2]+1)*(x.num[3]+1);
    for(i=0;i<bou;i++)
    	dp[i]=(double)100000000.000*(double)100000000.000;
   	p[0]=0;
    size=1;
    memset(heap[0].num,0,sizeof(heap[0].num));
    heap[0].f_value=0;
    heap[0].e_value=0;
    dp[0]=0;
	for(i=0;i<4;i++)
    {
    	if(heap[0].e_value<eval[i][x.num[i]])
    	   heap[0].e_value=eval[i][x.num[i]];   
    }  
    while(size)
    {
    	nw=heap[0];
    	id=nw.num[0]*(x.num[1]+1)*(x.num[2]+1)*(x.num[3]+1)+nw.num[1]*(x.num[2]+1)*(x.num[3]+1)+nw.num[2]*(x.num[3]+1)+nw.num[3];
    	heap[0]=heap[size-1];
    	if(nw.e_value==0)
    	   return nw.f_value;
		size--;
    	heapify(0);
		for(i=0;i<n;i++)
		{
  		    for(j=0;j<4;j++)
  		    	now.num[j]=min(x.num[j],nw.num[j]+there[i].num[j]);
 	        ip=now.num[0]*(x.num[1]+1)*(x.num[2]+1)*(x.num[3]+1)+now.num[1]*(x.num[2]+1)*(x.num[3]+1)+now.num[2]*(x.num[3]+1)+now.num[3];
 	        if(dp[ip]>dp[id]+there[i].pri)
 	        {
 	        	now.e_value=0;
 	        	for(j=0;j<4;j++)
 	        	{
 	        		if(now.e_value<eval[j][x.num[j]-now.num[j]])
 	        		   now.e_value=eval[j][x.num[j]-now.num[j]];
 	        	}
 	        	dp[ip]=dp[id]+there[i].pri;
 	        	now.f_value=dp[ip];
 	        	p[ip]=i+1;
 	        	rou[ip]=nw;
 	        	heap[size++]=now;
 	        	min_heapify(size-1);
 	        }
    	}
    } 
}
int main()
{
	int id,ip,tst=0,i,j,s,op;  
	while(scanf("%d",&n)&&n)
	{
		tst++; 
		for(i=0;i<n;i++)
		{
		   scanf("%d%lf",&there[i].id,&there[i].pri); 
		   memset(there[i].num,0,sizeof(there[i].num));
		   ch=getchar();
		   op=j=0;
		   while(ch!='\n')
		   { 
		   	   if(ch>='a'&&ch<='z')
		   	   {
				  there[i].num[j]+=op;		   	 
			      j=ch-'a';
		   	      op=0; 
		 	   }
		 	   else if(ch>='0'&&ch<='9')
  	               op=10*op+ch-'0'; 
		       ch=getchar();
		   } 
		   there[i].num[j]+=op;
		}
		sort(there,there+n,cmp);
		memset(ax,0,sizeof(ax));
		scanf("%d",&m);
		ch=getchar();
        j=0;		
		for(i=0;i<m;i++)
		{
			ch=getchar();
			memset(query[i].num,0,sizeof(query[i].num));
			j=op=0;
			while(ch!='\n')
			{
				if(ch>='a'&&ch<='z')
				{
					query[i].num[j]+=op;
					j=ch-'a';
				    op=0;
				}
				else if(ch>='0'&&ch<='9')
				    op=10*op+ch-'0';
				ch=getchar();
			}
			query[i].num[j]+=op;
   		    for(j=0;j<4;j++)
		    {
		      if(ax[j]<query[i].num[j])
		         ax[j]=query[i].num[j];
		    }
		}   
		for(i=0;i<4;i++)
		{
		  for(j=0;j<=ax[i];j++)
		     eval[i][j]=(double)100000000.000*(double)100000000.000;
		  eval[i][0]=0.000;
		}
		for(i=0;i<n;i++)
			for(j=0;j<4;j++)
			{
				for(s=0;s+there[i].num[j]<=ax[j];s++)
				{
					if(eval[j][s+there[i].num[j]]>eval[j][s]+there[i].pri)
					   eval[j][s+there[i].num[j]]=eval[j][s]+there[i].pri;
				}
			}
		for(i=0;i<4;i++)
		  for(j=ax[i];j>0;j--)
		  {
		  	if(eval[i][j-1]>eval[i][j])
		  	   eval[i][j-1]=eval[i][j];
		  }
		for(i=0;i<4;i++)
		   nw.num[i]=ax[i];
	    printf("Input set #%d:\n",tst);
		for(i=0;i<m;i++)
		{
		    printf("%d:%8.2lf",i+1,astar(query[i]));
	        memset(tnum,0,sizeof(tnum));
	        now=query[i];
			while(true)
	        {
	        	int ip=now.num[0]*(query[i].num[1]+1)*(query[i].num[2]+1)*(query[i].num[3]+1)+now.num[1]*(query[i].num[2]+1)*(query[i].num[3]+1)+now.num[2]*(query[i].num[3]+1)+now.num[3];
	        	if(p[ip]<=0)
	        	   break;
				tnum[p[ip]-1]++;
	        	now=rou[ip];
	        }
	        for(j=0;j<n;j++)
	        {
	        	if(tnum[j]>0)
	        	{
	        		printf(" %d",there[j].id);
	        	    if(tnum[j]>1)
	        	    	printf("(%d)",tnum[j]);
				}
	        }
	        printf("\n");
		}
	}
	return 0;
}

• Re:气死我了，怎么会WA,，这么优秀的算法。。。 (5238) JiaJunpeng 2010-04-23 20:00:11
  • Re:气死我了，怎么会WA,，这么优秀的算法。。。 (42) bankrupt 2010-04-23 20:06:12