1 dfsid+dp速度并不是很快！
2 #include<iostream>
3 #include<algorithm>
4 using namespace std;
5 int q,n;
6 bool dp[20001];
7 int num[101];
8 int ans[101];
9 int pre[101];
10 void dfsid(int Max,int dep)
11 {
12 if(dep==Max+1)
13 {
14 memset(dp,0,sizeof(dp));
15 dp[0]=1;
16 for(int i=1;i<=Max;++i)
17 for(int j=1;j<=q;++j)
18 if(j>=ans[i])dp[j]=dp[j]|dp[j-ans[i]];
19 if(dp[q])
20 {
21 printf("%d",Max);
22 sort(ans+1,ans+Max);
23 for(int i=1;i<=Max;++i)
24 printf(" %d",ans[i]);
25 printf("\n");
26 exit(0);
27 }
28 return ;
29 }
30 for(int i=pre[dep-1]+1;i<=n-Max+dep;++i)
31 {
32 ans[dep]=num[i];
33 pre[dep]=i;
34 dfsid(Max,dep+1);
35 }
36 }
37 int main()
38 {
39 freopen("milk4.in","r",stdin);
40 freopen("milk4.out","w",stdout);
41 scanf("%d%d",&q,&n);
42 for(int i=1;i<=n;++i)
43 scanf("%d",&num[i]);
44 for(int i=1;i<=n;++i)
45 {
46 pre[0]=0;
47 dfsid(i,1);
48 }
49 return 0;
50 }