SRM 651 Div2M: FoxAndSouvenirTheNext （動的計画法）

問題

おみやげがN個あり、それぞれvalue[i]の価値がある。2人におみやげの数が同じようになるように分けた時、価値の合計値が同じになるように分けることは可能か判定せよ。

解法

DPで[N/2][sum/2]の状態に到達可能か判定する。

コード

public class FoxAndSouvenirTheNext {

	public String ableToSplit(int[] value) {
		int N = value.length;
		if (N % 2 != 0) {
			return "Impossible";
		}

		int sum = 0;
		for (int i : value) {
			sum += i;
		}
		if (sum % 2 != 0) {
			return "Impossible";
		}

		boolean[][] dp = new boolean[N + 1][sum + 1];
		dp[0][0] = true;
		for (int i = 0; i < N; i++) {
			for (int x = i; x >= 0; x--) {
				for (int v = sum; v >= 0; v--) {
					if (dp[x][v]) {
						dp[x + 1][v + value[i]] = true;
					}
				}
			}
		}

		if (dp[N / 2][sum / 2]) {
			return "Possible";
		} else {
			return "Impossible";
		}

	}
}