35个数字意味着2^35种可能性，穷举是不可能的，因此我们采用二分搜索。 首先枚举一半的可能性存入map容器中，并不断更新答案，因为有可能这一部分中的答案就是最后的答案。同样枚举另一半的可能性，更新答案，但是要注意与上一部份的答案相结合。
#include <cstdio> #include <map> #include <algorithm> using namespace std; typedef pair<long long, int> P; long long a[40]; long long abs(long long x) { return x >= 0 ? x : -x; } int main(int argc, char const *argv[]) { int n; while (scanf("%d", &n) == 1 && n) { for (int i = 0; i < n; i++) { scanf("%lld", &a[i]); } map<long long, int> mp; //保存答案：最小绝对值及选取个数 P res = make_pair(abs(a[0]), 1); for (int i = 1; i < (1 << (n / 2)); i++) { long long sum = 0; int cnt = 0; for (int j = 0; j < n / 2; j++) { if ((i >> j) & 1) { sum += a[j]; cnt++; } } //只从前半部分选取答案 res = min(res, make_pair(abs(sum), cnt)); if (mp[sum] != 0) { mp[sum] = min(mp[sum], cnt); } else { mp[sum] = cnt; } } for (int i = 1; i < (1 << (n - n / 2)); i++) { long long sum = 0; int cnt = 0; for (int j = 0; j < n - n / 2; j++) { if ((i >> j) & 1) { sum += a[n/2+j]; cnt++; } } //只从后半部分选取答案 res = min(res, make_pair(abs(sum), cnt)); //同时从两个部分选取答案 map<long long, int> :: iterator ite; ite = mp.lower_bound(-sum); if (ite != mp.end()) { res = min(res, make_pair(abs(ite->first + sum), ite->second + cnt)); } if (ite != mp.begin()) { ite--; res = min(res, make_pair(abs(ite->first + sum), ite->second + cnt)); } } printf("%lld %d\n", res.first, res.second); } return 0; }