P1441 砝码称重

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int w[21];
 7 bool f[2010];
 8 bool th[21];
 9 int n, m;
10 int maxn;
11 
12 void dp()
13 {
14     memset(f, false, sizeof(f));
15     int cnt = 0;
16     int sum = 0;
17     f[0] = true;
18     for (int i = 1; i <= n; i++)
19     {
20         if (th[i]) continue;
21         for (int j = sum; j >= 0; j--)
22         {
23             if (f[j] && !f[j + w[i]])
24             {
25                 f[j + w[i]] = true;
26                 cnt++;
27             }
28         }
29         sum += w[i];
30     }
31     maxn = max(maxn, cnt);
32 }
33 
34 
35 void dfs(int num, int now)
36 {
37     if (m < now) return;
38     if (num == n + 1)
39     {
40         if (now == m)
41         {
42             dp();
43         }
44         return;
45     }
46     th[num] = true;
47     dfs(num + 1, now + 1);
48     th[num] = false;
49     dfs(num + 1, now);
50 }
51 
52 int main()
53 {
54     cin >> n >> m;
55     for (int i = 1; i <= n; i++)
56     {
57         cin >> w[i];
58     }
59     dfs(1, 0);
60     cout << maxn;
61 }