#include "stdio.h"
int c,b,n,w[23][4],cw,bestw,sta[8];
long r=0;
void backtrack(int i)
{int flag=1,j;
if(i>n)
	{if(cw>bestw) bestw=cw;
	return ;
	}
 r-=w[i][3];
 for(j=w[i][0];j<w[i][1];j++)
	 if(sta[j]+w[i][2]>c) {flag=0;break;}
 if(flag)
	{for(j=w[i][0];j<w[i][1];j++) sta[j]+=w[i][2];
	cw+=w[i][3];
	backtrack(i+1);
	cw-=w[i][3];
	for(j=w[i][0];j<w[i][1];j++) sta[j]-=w[i][2];
	}
 if(cw+r>bestw)
	backtrack(i+1);
 r+=w[i][3];
}
int main(int argc, char* argv[])
{int i;
 while(scanf("%d %d %d",&c,&b,&n),c!=0&&b!=0&&n!=0)
	{r=0;bestw=0;cw=0;
	 for(i=1;i<=n;i++)
		{scanf("%d %d %d",&w[i][0],&w[i][1],&w[i][2]);
		w[i][3]=(w[i][1]-w[i][0])*w[i][2];	
	     r+=w[i][3];
		}
	for(i=0;i<=b;i++) sta[i]=0;
	backtrack(1);
	printf("%d\n",bestw);
	}
	return 0;
}

• Re:哪位高人给看看哪错了？用回溯法做的。 (22) yipingan 2008-08-30 01:00:07