import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.StringTokenizer; public class DividingCoins { public static class InputReader { private BufferedReader reader; private StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream)); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public long nextLong() { return Long.parseLong(next()); } public int nextInt() { return Integer.parseInt(next()); } } public static void main(String[] args) { InputReader in = new InputReader(System.in); int T = in.nextInt(); while (T-- != 0) { int N = in.nextInt(); int[] A = new int[N]; int sum = 0; for (int n = 0; n < N; n++) { A[n] = in.nextInt(); sum += A[n]; } int column = 0; boolean[][] B = new boolean[sum / 2 + 1][N + 1]; for (int i = 0; i < N + 1; i++) { B[0][i] = true; } for (int i = 0; i < A.length; i++) { for (int j = 0; j <= sum / 2; j++) { if (B[j][i]) { B[j][i + 1] = true; if ((j + A[i]) <= sum / 2) { B[j + A[i]][i + 1] = true; } } } } int count = 0; for (int i = sum / 2; i >= 0; i--) { if (B[i][A.length]) break; count++; } System.out.println((sum % 2 == 0) ? 2 * count : 2 * count + 1); } } }
Sample Input:
11 3 2 2 1 4 5 5 2 2 3 6 7 8 4 2 3 4 5 2 24 12 2 1 1 12 1 2 3 4 5 6 7 8 9 10 11 12 4 2 3 4 19 5 3 4 2 1 11 3 10 20 30 4 5 6 3 12
Sample Output:
1 0 5 0 12 0 0 10 1 0 2