最后来遍历一遍分数，判断 $dp[n >> 1][i]$ 可不可行即可。
## 代码：
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
int n;
int a[107];
int dp[107][10007];
int sum;
inline int maxa(int a, int b) {
if (a > b)
return a;
return b;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
sum += a[i];
}
dp[0][0] = 1;
for (int i = 1; i <= n; i ++) {
for (int j = i; j >= 1; j --) {
for (int k = sum >> 1; k >= a[i]; k --)
dp[j][k] |= dp[j - 1][k - a[i]];
}
}
for (int i = sum >> 1; i >= 0; i --) {
if (dp[n >> 1][i]) {
printf("%d\n", i);
return 0;
}
}
}
```
## 结语：
麻烦管理员，请允许我废话几句，我怕以后就没博客发上来了。
其实学 OI 到现在，我也不明白为什么在 1 年前已经被淘汰时还要再坚持，或许只是内心的执着，亦或是内心的不甘，然而在新的一年 csp 的前一个月，我终究还是在纠结着要不要参加，学 OI 或许要抵抗许许多多的障碍，家长就是一个难过的关，可能由于家长，我没法去今年的 csp，但我还是祝愿学 OI 的那些巨佬们说：
$Wish$ $you$ $never$ $grow$ $old$.
算是勉励自己吧。