记录编号	135003	评测结果	AAAAA
题目名称	[NOIP 2001PJ]装箱问题	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2014-10-31 14:28:35	内存使用	0.36 MiB

#include<cstdio>
#include<cctype>
using namespace std;

int ret;
char ch;
int qin()
{
    ret=0;
    while(ch=getchar(),!isdigit(ch));
    while(ret=ret*10+ch-'0',ch=getchar(),isdigit(ch));
    return ret;
}

int m,n;
int w[31];
int f[20001];

int main()
{
    freopen("npack.in","r",stdin);
    freopen("npack.out","w",stdout);
	m=qin();n=qin();
	for(int i=1;i<=n;i++) w[i]=qin();
	for(int i=1;i<=n;i++)
	{
		for(int v=m;v>=w[i];v--)
		{
			if(f[v-w[i]]+w[i]>f[v])
				f[v]=f[v-w[i]]+w[i];
		}
	}
	printf("%d\n",m-f[m]);
    return 0;
}