POJ - 3977 Subset(折半枚举)

Subset Time Limit: 30000MS Memory Limit: 65536KTotal Submissions: 3193 Accepted: 570

Description

Given a list of N integers with absolute values no larger than 10 ¹⁵, find a non empty subset of these numbers which minimizes the absolute value of the sum of its elements. In case there are multiple subsets, choose the one with fewer elements.

Input

The input contains multiple data sets, the first line of each data set contains N <= 35, the number of elements, the next line contains N numbers no larger than 10 ¹⁵ in absolute value and separated by a single space. The input is terminated with N = 0

Output

For each data set in the input print two integers, the minimum absolute sum and the number of elements in the optimal subset.

Sample Input

1 10 3 20 100 -100 0

Sample Output

10 1 0 2 题意:从N个数中选出几个数构成一个子集，让这个子集内的元素和的绝对值最小，如果有多个情况，输出子集元素数目最少的。 折半枚举，即枚举法和二分查找法的综合，而对于折半枚举法，个人理解为对一些数据预处理出他的数据，然后用一个循环枚举另一些数据，然后用二分在之前预处理出的数据中查找满足条件的数据。 /*头文件模板*/ #include <map> #include <set> #include <cmath> #include <ctime> #include <queue> #include <vector> #include <cctype> #include <cstdio> #include <string> #include <cstring> #include <sstream> #include <cstdlib> #include <iomanip> #include <typeinfo> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define pb push_back #define mp make_pair #define mem(a, x) memset(a, x, sizeof(a)) #define copy(a, b) memcpy(a, b, sizeof(a)) #define lson rt << 1, l, mid #define rson rt << 1|1, mid + 1, r #define FIN freopen("input.txt", "r", stdin) #define FOUT freopen("output.txt", "w", stdout) typedef long long LL; typedef pair<int, int > PII; typedef pair<int, string> PIS; typedef pair<LL, LL> PLL; typedef pair<LL, int> PLI; typedef unsigned long long uLL; template<typename T> void print (T* p, T* q, string Gap = " ", bool flag = false) { int d = p < q ? 1 : -1; while (p != q) { if (flag) cout << Gap[0] << *p << Gap[1]; else cout << *p; p += d; if (p != q && !flag) cout << Gap; } cout << endl; } template<typename T> void print (const T &a, string bes = "") { int len = bes.length(); if (len >= 2) cout << bes[0] << a << bes[1] << endl; else cout << a << endl; } void IO_Init() { ios::sync_with_stdio (false); } LL LLabs (LL a) { return a >= 0 ? a : -a; } const double PI = 3.1415926535898; const double eps = 1e-10; const int MAXM = 1e5 + 5; const int MAXN = 35 + 5; const LL INF = 1e17; /*头文件模板*/ int N; LL A[MAXN]; map<LL, int>dp; int main() { //FIN; while(~scanf("%d", &N), N) { dp.clear(); for(int i = 0; i < N; i ++) { scanf("%lld", &A[i]); } PLI res(LLabs(A[0]), 1); for(int i = 1; i < (1 << (N / 2)); i ++) { LL sum = 0; int num = 0; for(int j = 0; j < N / 2; j ++) { if((i >> j) & 1) { sum += A[j]; num ++; } } res = min(res, PLI(LLabs(sum), num)); map<LL, int>::iterator it = dp.find(sum); if(it != dp.end()) { it -> second = min(it -> second, num); } else { dp[sum] = num; } } for(int i = 1; i < (1 << (N - N / 2)); i ++) { LL sum = 0; int num = 0; for(int j = 0; j < N - N / 2; j ++) { if((i >> j) & 1) { sum += A[N / 2 + j]; num ++; } } res = min(res, PLI(LLabs(sum), num)); map<LL, int>::iterator it = dp.lower_bound(-sum); if(it != dp.end()) { res = min(res, PLI(LLabs(sum + it -> first), num + it -> second)); } if(it != dp.begin()) { it --; res = min(res, PLI(LLabs(sum + it -> first), num + it -> second)); } } printf("%lld %d\n", res.first, res.second); } return 0; }