记录编号	41433	评测结果	AAAAAAAAAAA
题目名称	946.待售干草	最终得分	100
用户昵称	yuan	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2012-07-22 22:17:17	内存使用	13.68 MiB

#define MAX 5000
#include <fstream>
#include <cstdlib>
using namespace std;

int mx=0,c=0,h=0,v[MAX]={0};
ifstream fin("hay4sale.in");
ofstream fout("hay4sale.out");
int doing(int i,int tc)
{
	if(tc>mx&&tc<=c)mx=tc;//更新最优值
	if(mx==c)
	{
		fout<<c<<endl;exit(0);//如果等于最大容量，输出并直接退出
	}
	if(i<=h)
	{
		if(tc+v[i]<=c)doing(i+1,tc+v[i]);//装上第i种草并尝试下一种草
		if(tc<=c)doing(i+1,tc);//不装第i种草，直接尝试下一种草
	}
	return 0;
}

int main ()
{
	int i;
	fin>>c>>h;
	for(i=1;i<=h;i++)fin>>v[i];
	doing(1,0);//在当前容量是0的情况下开始尝试第1种干草
	fout<<mx<<endl;
	fin.close();
	fout.close();
	return 0;
}