POJ-3977 : Subset

問題概要

N(<35)個の整数が与えられる。非空の部分集合を作って和が0にもっとも近くなるようなものをつくり、またそのような作り方が複数ある時はサイズが最小になるようにせよ。

解法

半分全列挙だけど、0を適当に取り除いたりユニークしたりする。

acceptされたコード

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;

const int64 INF = 1LL<<60;
const int MAX_N = 36;

int N, L;
int64 as[MAX_N];
pair<int64, int> ts[1<<(MAX_N/2)];

bool init() {
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%lld", as + i);
	}
	return N > 0;
}

void solve() {
	if (N == 1) {
		printf("%lld 1\n", abs(as[0]));
		return ;
	}

	L = 0;
	for (int bit = 0; bit < 1<<(N-N/2); ++bit) {
		int64 tmp = 0;
		for (int i = 0; i < N-N/2; ++i) if ( (bit>>i)&1 ) {
			tmp += as[N/2 + i];
		}
		ts[L++] = make_pair(tmp, __builtin_popcount(bit));
	}

	pair<int64, int> ans(INF, 0);

	sort(ts, ts + L);
	for (int i = 0; i < L; ++i) {
		if( ts[i] != make_pair(0LL, 0) ) {
			ans = min( ans, make_pair(abs(ts[i].first), ts[i].second) );
		}
		if (i > 0 && ts[i].first == ts[i-1].first) {
			ts[i].second = ts[i-1].second;
		}
	}
	sort(ts, ts + L);
	L = unique(ts, ts + L) - ts;

	for (int bit = 0; bit < 1<<(N/2); ++bit) {
		int64 tmp = 0;
		for (int i = 0; i < N/2; ++i) if ((bit>>i)&1) {
			tmp += as[i];
		}
		int p = lower_bound(ts, ts + L, make_pair(-tmp, 0)) - ts;
		for (int i = -1; i <= 1; ++i) {
			if (0 <= p + i && p + i < L) {
				pair<int64, int> t(abs(tmp + ts[p + i].first), __builtin_popcount(bit) + ts[p + i].second);
				if (t.second > 0 && t < ans) {
					ans = t;
				}
			}
		}
	}

	printf("%lld %d\n", ans.first, ans.second);
}

int main() {
	for (; init(); ) {
		solve();
	}

	return 0;
}