UVa 624

　　题目大意：有n首歌曲要录制到磁带上，每首歌长a_i分钟，磁带可录制l分钟的歌曲。

　　由于n<=20，如果暴力枚举的话复杂度为O(2²⁰⁾, 2²⁰约等于10⁶，在可接受范围内。

 1 #include <cstdio>
 2 #include <vector>
 3 using namespace std;
 4 
 5 vector<int> t, ans;
 6 int a[25];
 7 int tape, n;
 8 int sum, lmax;
 9 
10 void dfs(int cur)
11 {
12     if (cur == n)
13     {
14         if (sum > lmax) 
15         {
16             lmax = sum;
17             ans.clear();
18             for (int i = 0; i < t.size(); i++)
19                 ans.push_back(t[i]);
20         }
21         return;
22     }
23     dfs(cur+1);
24     if (sum + a[cur] <= tape)
25     {
26         sum += a[cur];
27         t.push_back(a[cur]);
28         dfs(cur+1);
29         t.pop_back();
30         sum -= a[cur];
31     }
32 }
33 
34 int main()
35 {
36 #ifdef LOCAL
37     freopen("in", "r", stdin);
38 #endif
39     while (scanf("%d", &tape) != EOF)
40     {
41         scanf("%d", &n);
42         for (int i = 0; i < n; i++)
43             scanf("%d", &a[i]);
44         sum = 0;
45         lmax = -1;
46         dfs(0);
47         for (int i = 0; i < ans.size(); i++)
48             printf("%d ", ans[i]);
49         printf("sum:%d
", lmax);
50     }
51     return 0;
52 }

View Code

　　上面这个代码用时45ms，还不是很大^_^。也可以用dp，当成0-1背包问题进行求解。