1 #include <iostream>
2 #include <cstdlib>
3 #include <cstdio>
4 #include <algorithm>
5 #include <cstring>
6 using namespace std;
7 const int MAX_NUM = 25;
8 const int MAX_N = 100005;
9 struct node {
10 int t_n; // 得到它前面那个所取节点的位置
11 bool Judge; // 判断当前节点是否被选择
12 };
13 int N, num;
14 int dp[MAX_NUM][MAX_N], arr[MAX_NUM];
15 node vis[MAX_NUM][MAX_N];
16
17 void output(int mynum, int myN, int sum) {
18 if (sum == 0) {
19 return;
20 }
21 if (vis[mynum][myN].Judge) {
22 output(mynum - 1, vis[mynum][myN].t_n, sum - arr[mynum]);
23 printf("%d ", arr[mynum]);
24 }
25 else {
26 output(mynum - 1, myN, sum);
27 }
28 }
29
30 void Solve() {
31 for (int i = 1; i <= num; ++i) {
32 for (int k = 0; k < arr[i]; ++k) {
33 dp[i][k] = dp[i - 1][k];
34 }
35 for (int j = arr[i]; j <= N; ++j) {
36 if (dp[i - 1][j - arr[i]] + arr[i] > dp[i - 1][j]) {
37 dp[i][j] = dp[i - 1][j - arr[i]] + arr[i];
38 vis[i][j].Judge = true;
39 vis[i][j].t_n = j - arr[i];
40 }
41 else { dp[i][j] = dp[i - 1][j]; }
42 }
43 }
44
45 int start;
46 for (start = num; start >= 0; --start) {
47 if (vis[start][N].Judge) {
48 break;
49 }
50 }
51 output(start, N, dp[start][N]);
52
53 printf("sum:%d
", dp[num][N]);
54 }
55
56 int main()
57 {
58 //freopen("input.txt", "r", stdin);
59 while (~scanf("%d %d", &N, &num)) {
60 for (int i = 0; i <= num; ++i) {
61 for (int j = 0; j <= N; ++j) {
62 dp[i][j] = 0;
63 vis[i][j].Judge = false;
64 vis[i][j].t_n = -1;
65 }
66 }
67 for (int i = 1; i <= num; ++i) {
68 scanf("%d", &arr[i]);
69 }
70 Solve();
71 }
72 return 0;
73 }
