题目链接：http://poj.org/problem?id=3977
题意：给你n个数，求出这n个数的一个非空子集，使子集中的数加和的绝对值最小，在此基础上子集中元素的个数应最小。
思路：n为35，直接枚举的复杂度肯定是容不下的。但我们可以把这些数分为两半，算出前一半元素所有子集对应的权和及个数，对后一半元素的每个子集，设其元素之和为sum，用二分查找的方法在前一半中找元素和最接近-sum的子集即可。
#include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; typedef pair<ll, ll> P; map<ll, int> mp; ll a[50]; ll Abs(ll x) { return x < 0 ? -x : x; } bool input(int& n) { cin >> n; if(n == 0) return false; for(int i = 0; i < n; i++) cin >> a[i]; mp.clear(); return true; } void solve(int n) { P ans = P(Abs(a[0]), 1); map<ll, int> :: iterator it; int mid = n >> 1; //枚举前半部分 for(int i = 0; i < 1<<mid; i++) { ll sum = 0; int num = 0; for(int j = 0; j < mid; j++) if(i >> j & 1) { sum += a[j]; ++num; } if(num == 0) continue; ans = min(ans, P(Abs(sum), num)); //全在前半段 // 插入map it = mp.find(sum); if(it != mp.end()) it->second = min(it->second, num); else mp[sum] = num; } //枚举后半部分 for(int i = 0; i < 1<<(n-mid); i++) { ll sum = 0; int num = 0; for(int j = 0; j < n-mid; j++) if(i >> j & 1) { sum += a[j+mid]; ++num; } if(num == 0) continue; ans = min(ans, P(Abs(sum), num)); //全在后半段 //在map中寻找答案 it = mp.lower_bound(-sum); //使这两半的和的绝对值最小，前半段要尽量接近-sum if(it != mp.end()) ans = min(ans, P(Abs(sum + it->first), it->second + num)); if(it != mp.begin()) --it, ans = min(ans, P(Abs(sum + it->first), it->second + num)); } //输出答案 cout << ans.first << ' ' << ans.second << endl; } int main() { int n; while(input(n)) { solve(n); } return 0; }
