记录编号	104265	评测结果	AAAAA
题目名称	[NOIP 2001PJ]装箱问题	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2014-06-04 17:42:20	内存使用	0.39 MiB

#include <iostream>
#include <cstdio>

using namespace std;

int Backpack[20001];
int Weight[31];
int N=0,M=0;

void IN();
void BAG();
void OUT();

int main()
{
	freopen("npack.in","r",stdin );
	freopen("npack.out","w",stdout);
	IN();
	BAG();
	OUT();
	return 0;
}

void IN()
{
	cin >> M >> N;
	for (int i=1;i<=N;i ++ )
	{
		cin >> Weight[i];
	}
}

void BAG()
{
	for (int i=1;i<=N;i ++ )
	{
		for (int j=M;j>=Weight[i];j -- )
		{
			if (Backpack[j-Weight[i]]+Weight[i] > Backpack[j])
			Backpack[j]=Backpack[j-Weight[i]]+Weight[i];
		}
	}
}

void OUT()
{
	cout << M-Backpack[M] << endl;
}