首页 > 代码库 > poj 3977 Subset
poj 3977 Subset
Subset
Time Limit: 30000MS | Memory Limit: 65536K | |
Total Submissions: 3662 | Accepted: 673 |
Description
Given a list of N integers with absolute values no larger than 1015, 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 1015 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个数,从中挑选出一个子集,使得该子集中所有元素的和为所有子集当中最小,输出子集的和,以及子集的个数。
思路:折半搜索,n个数可以分成两个元素个数相当的区域,对于第一个区域,进行穷举每一种情况(取出该区域的每个子集),并将每种情况的和sum以及元素个数num记录在map表中,在第二个区域中,也穷举每种情况,对于每种情况得到的SUM,在区域1中进行二分搜索,即在
区域1中所有的sum值中找到一个和(-SUM)值最接近的值,找到之后|sum+SUM|就是需要求的整个序列的最小值,总个数即两个区域子集分别的个数相加即可。
AC代码:
#define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<algorithm> #include<string> #include<cmath> #include<map> using namespace std; typedef long long ll; const int N_MAX = 35 + 1; ll number[N_MAX]; ll ll_abs(const ll&a) { return a >= 0 ? a : -a; } int main() { int n; while (scanf("%d",&n)&&n) { for (int i = 0; i < n; i++) { scanf("%lld", &number[i]); } map<ll, int>m;//sum<->num pair<ll, int>opt(ll_abs(number[0]),1);//存储最优解 for (int i = 0; i < 1 << (n / 2); i++) {//先枚举前n/2个 ll sum=0; int num = 0; for (int j = 0; j < n / 2; j++) { if (i&(1 << j)) { sum += number[j]; num++; } } if (num == 0)continue; opt = min(opt,make_pair(ll_abs(sum),num));//最优解的sum是绝对值,一定大于等于0 map<ll, int>::iterator it = m.find(sum); if (it != m.end()) { it->second = min(it->second, num);/////元素个数尽量少 } else m[sum] = num;//////!!!!!!!!!!!!!!!!!!!!!!!!!!!!新的数据 } //在对后n/2个数据进行二分查找 for (int i = 0; i < 1<<(n - n / 2); i++) { ll sum = 0; int num = 0; for (int j = 0; j < n - n / 2; j++) { if (i&(1 << j)) { sum += number[n / 2 + j]; num++; } } if (num == 0)continue; opt = min(opt, make_pair(ll_abs(sum), num)); map<ll, int>::iterator it = m.lower_bound(-sum);//返回大于等于-sum的元素 if (it != m.end()) {//此时it->first一定比-sum大 opt = min(opt, make_pair(ll_abs(it->first + sum),it->second+num)); } if (it != m.begin()) {//可能it->first比-sum小一点,也有可能产生一个最小值 it--; opt = min(opt, make_pair(ll_abs(it->first + sum), it->second + num)); } } cout << opt.first << " " << opt.second << endl; } return 0; }
poj 3977 Subset
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。