记录编号	45078	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Nescafé 26] 小猫爬山	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2012-10-22 11:14:55	内存使用	1.96 MiB

#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=20;
int N,W,M,weight[MAXN],Now[MAXN];
bool cmp(const int&a,const int&b){return a>b;}

inline void init()
{
	scanf("%d %d\n",&N,&W);
	for(int i=1;i<=N;i++) scanf("%d",&weight[i]);
	sort(weight+1,weight+1+N,cmp);
}

bool dfs(int k)
{
	if(k>N) return 1; 
	for(int i=1;i<=M&&i<=k;i++)
	{
		if(Now[i]+weight[k]>W) continue;
		Now[i]+=weight[k];  
		if(dfs(k+1)) return 1;
		Now[i]-=weight[k];
	} return 0;
}

inline void search()
{
	for(;M<=N;M++)
	{
		memset(Now,0,sizeof(Now));
		if(dfs(1)) break;
	}
	printf("%d\n",M);
}

int main()
{
	freopen("koneko.in","r",stdin);
	freopen("koneko.out","w",stdout);
	init(); search();
	return 0;
}