1 /************************************************************** 2     Problem: 1334 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:156 ms 7     Memory:1196 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <algorithm>12  13 using namespace std;14  15 int n, sum, ans;16 int a[305];17 int f[100005];18  19 int main() {20     int i, j;21     scanf("%d", &n);22     for (i = 1; i <= n; ++i)23         scanf("%d", a + i), sum += a[i];24     sort(a + 1, a + n + 1);25     f[0] = 1;26     for (i = n; i; --i)27         for (j = sum / 2 + a[i]; j >= a[i]; --j)28             if (f[j - a[i]])29                 f[j] = 1, ans = max(j, ans);30     printf("%d\n", ans);31     return 0;32 }