PKU 3172 Scales

• 枝刈り探索
• 計算量は不明

int N, C;
ll weights[1024];
ll sumWeights[1024];
ll bestAnswer = 0;
void dfs(int i, ll value) {
	if (value + sumWeights[i] <= bestAnswer) {
		return;
	}

	bestAnswer = max(bestAnswer, value);
	if (i == N) {
		return;
	}

	if (value + weights[i] <= C) {
		dfs(i + 1, value + weights[i]);
	}
	dfs(i + 1, value);
}

int main() {
	memset(weights, 0, sizeof(weights));
	memset(sumWeights, 0, sizeof(sumWeights));

	cin >> N >> C;
	REP(n, N) {
		cin >> weights[n];
	}

	reverse(weights, weights + N);

	for (int n = N - 1; n >= 0; --n) {
		sumWeights[n] = weights[n] + sumWeights[n + 1];
	}

	dfs(0, 0);

	cout << bestAnswer << endl;
}