记录编号	317193	评测结果	AAAAAATTAT
题目名称	量取牛奶	最终得分	70
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	3.128 s
提交时间	2016-10-07 19:18:36	内存使用	17.10 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
const int maxn=110,maxv=20010;
void dfs(int,int);
int n,v,w[maxn],f[maxn][maxv][2],ans;
bool vis[maxv];
int a[maxn],b[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("milk4.in","r",stdin);
	freopen("milk4.out","w",stdout);
#endif
	scanf("%d%d",&v,&n);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);
	memset(f,63,sizeof(f));
	f[0][0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=v;j++)f[i][j][0]=min(f[i-1][j][0],f[i-1][j][1]);
		for(int j=w[i];j<=v;j++)f[i][j][1]=min(min(f[i-1][j-w[i]][0]+1,f[i-1][j-w[i]][1]+1),min(f[i][j-w[i]][0]+1,f[i][j-w[i]][1]));
	}
	ans=min(f[n][v][0],f[n][v][1]);
	printf("%d",ans);
	sort(w+1,w+n+1);
	dfs(1,0);
	for(int i=1;i<=ans;i++)printf(" %d",b[i]);
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#else
	fclose(stdin);
	fclose(stdout);
#endif
	return 0;
}
void dfs(int i,int cnt){
	if(cnt==ans){
		fill_n(vis+1,v,false);
		vis[0]=true;
		for(int j=1;j<=v;j++)for(int k=1;k<=cnt;k++)if(j>=a[k])vis[j]|=vis[j-a[k]];
		if(vis[v]){
			memcpy(b,a,sizeof(a));
			return;
		}
	}
	if(i>n)return;
	a[cnt+1]=w[i];
	dfs(i+1,cnt+1);
	if(b[1])return;
	dfs(i+1,cnt);
}
/*
16 3 3 5 7
Answer:
2 3 5
*/