ZOJ Monthly, July 2012 - J : Watashi's BG

問題概要

長さN(<30)の配列Xがある。Xの部分和でMを越えない最大のものを求める問題。

解法

半分全列挙でよい。

acceptされたコード

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

typedef long long int64;

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

int N, M;
int as[MAX_N];
int64 nums[(1<<(MAX_N/2)) + 2];

bool init() {
	if (scanf("%d%d", &N, &M) == EOF) {
		return false;
	}

	for (int i = 0; i < N; ++i) {
		scanf("%d", as + i);
	}

	return N > 0;
}

int solve() {
	if (N == 1) {
		return as[0] <= M ? as[0] : 0;
	}

	const int half = N / 2;
	int L = 0;
	for (int bit = 0; bit < (1<<half); ++bit) {
		nums[L] = 0;
		for (int i = 0; i < half; ++i) if ((bit>>i)&1) {
			nums[L] += as[i];
		}
		++L;
	}
	nums[L++] = -INF;

	sort(nums, nums + L);
	reverse(nums, nums + L);
	int64 ans = -INF;
	for (int bit = 0; bit < (1<<(N-half)); ++bit) {
		int64 tmp = 0;
		for (int i = 0; i < N-half; ++i) if ((bit>>i)&1) {
			tmp += as[i+half];
		}
		tmp += *lower_bound(nums, nums + L, M - tmp, greater<int64>());
		if (tmp <= M && ans < tmp) {
			ans = tmp;
		}
	}

	return (int)ans;
}

int main() {
	for (;init();) {
		printf("%d\n", solve());
	}
	return 0;
}