选课.cpp

来自「有关算法设计与分析的几个小程序（查找与替换问题、炒饭问题、寻宝问题等）」· C++ 代码 · 共 42 行

#include<stdio.h>
int n,sw,p[51],w[51],cp,cw,bestp;
int x[51];
void score(int i,int cp,int cw)
{
//	int j;
	if(cw>sw)
		return;

	if(i>=n)
	{
		bestp=bestp>=cp?bestp:cp;
		return;
	}
/*	else 
		for(j=0;j<=1;j++)
		{
			x[i]=j;
			if(cw+x[i]*w[i]<=sw)
				score(i+1,cp+p[i]*x[i],cw+w[i]*x[i]);
		}
		*/

	score(i+1,cp+p[i],cw+w[i]);
	score(i+1,cp,cw);
}

main()
{
	int i;
	while(scanf("%d%d",&n,&sw)!=EOF)
	{
		for(i=0;i<n;i++)
			scanf("%d%d",&p[i],&w[i]);
		bestp=0;
		score(0,0,0);
		printf("%d\n",bestp);
	}
	return 0;
}