题目来源：UVA 624
题目的意思就是：我现在需要从 t 张CD中拿出一部分来，尽可能的凑出接近 N 这么久的音乐，但是不能超过 N。
CD不超过20张，每张长度不超过 N ，不能重复选。
一个很简单的0-1背包。因为最多只有220 = 1048576种可能，所以即使是枚举所有情况都可以毫无压力的搞起。
我这里用的DFS进行枚举，然后得到最好的结果。
最后需要说的是，此题是特判的。输出CD的长度的时候是无序的。
附AC代码：
1: #include <stdio.h>
2: #include <iostream>
3: #include <math.h>
4: #include <stdlib.h>
5: #include <string.h>
6: #include <algorithm>
7: #include <string>
8: #include <vector>
9: using namespace std;
10:
11: int t, n, pri[29], res[29], tmp[29], sum = 0;
12:
13: void dfs(int id)
14: {
15: if (id > n)
16: {
17: int m = 0;
18: for (int i = 1; i <= n; i++)
19: if (tmp[i])
20: m += pri[i];
21: if (m > sum && m <= t)
22: {
23: sum = m;
24: for (int i = 1; i <= n; i++)
25: res[i] = tmp[i];
26: }
27: return;
28: }
29: else
30: {
31: tmp[id] = 1;
32: dp(id+1);
33: tmp[id] = 0;
34: dp(id+1);
35: return;
36: }
37: }
38:
39: int main()
40: {
41: while (~scanf("%d%d", &t, &n))
42: {
43: memset(res, 0, sizeof(res));
44: memset(tmp, 0, sizeof(tmp));
45: memset(pri, 0, sizeof(pri));
46: sum = 0;
47: for (int i = 1; i <= n; i++)
48: scanf("%d", &pri[i]);
49: dfs(1);
50: for (int i = 1; i <= n; i++)
51: if (res[i])
52: printf("%d ", pri[i]);
53: printf("sum:%d\n", sum);
54: }
55: }