poj 3977 Subset 折半枚举

题意：

给n（n<=35）个数，求一个它的子集，使其中元素和的绝对值最小。

分析：

折半枚举。

代码：

//poj 3977
//sep9
#include <iostream>
#include <map>
using namespace std;
typedef long long LL;
const int maxN=40;
LL a[maxN];
LL myabs(LL x)
{
	return x>=0?x:-x;
}
int main()
{
	int n;
	while(cin>>n&&n){
		for(int i=0;i<n;++i)
			cin>>a[i];
		map<LL,int> m; 
		pair<LL,int> res(myabs(a[0]),1);
		for(int i=0;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;
				}
			if(!num) continue;
			res=min(res,make_pair(myabs(sum),num));		
			map<LL,int>::iterator iter=m.find(sum);
			if(iter!=m.end())
				iter->second=min(iter->second,num);
			else 
				m[sum]=num;
		}
		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>>j)&1){
					sum+=a[n/2+j];
					++num;
				}
			if(!num) continue;
			res=min(res,make_pair(myabs(sum),num));
			map<LL,int>::iterator iter=m.lower_bound(-sum);
			if(iter!=m.end())
				res=min(res,make_pair(myabs(sum+iter->first),num+iter->second));
			if(iter!=m.begin()){
				--iter;
				res=min(res,make_pair(myabs(sum+iter->first),num+iter->second));
			}
		}
		cout<<res.first<<" "<<res.second<<endl;
	}
	return 0;	
} 

poj 3977 Subset 折半枚举

原文：http://blog.csdn.net/sepnine/article/details/44536145