高橋君とお肉 [ AtCoder Regular Contest 029 A ]

atcoder.jp

問題

N 個の数字を A,B の2つのグループに分ける。
Aグループに属する数字の合計を sumA 、Bグループに属する数字の合計を sumB とする。

sumA, sumB の差が最小になるようにグループ分けをするとき、sumA, sumB のうち大きいほうを出力せよ。

考察

DPの解法もあるみたいですが、素直に全探索します。
N は 1<=N<=4 なので組み合わせの数は最大でも 2^4=16 となり間に合います。

それぞれの肉について、Aに属するかBに属するかをビット全探索で探索し、差が最小となるような組み合わせを求めます。

コード

void solve (FastScanner in, PrintWriter out) {

	int n = in.nextInt();
	int[] niku = in.nextIntArray(n);
	
	int min = Integer.MAX_VALUE;
	
	for (int bit=0; bit<(1<<n); bit++) {
		
		int sum1 = 0, sum2 = 0;
		
		for (int j=0; j<n; j++) {
			if (((bit>>j) & 1) == 1) {
				sum1 += niku[j];
			}
			else {
				sum2 += niku[j];
			}
		}

		min = Math.min(min, Math.max(sum1, sum2));
		
	}
	
	out.println(min);
	
}