/************************************************************************* * Compilation: javac Schedule.java * Execution: java Schedule N < data.txt * * This programs takes a command line parameter N, reads in N * positive real numbers from standard input, and partitions them into * two groups so that the difference in their sums is minimized. * * % java Schedule 4 < test.txt * -1.41 * 1.73 * 2.00 * -2.23 * Difference: 0.09 * *************************************************************************/ public class Schedule { public static void moves(int n, double[] a, double[] b) { if (n == 0) return; moves(n-1, a, b); // flip whether or not a[n] is in the subset a[n] = -a[n]; a[0] += 2*a[n]; if (Math.abs(a[0]) < Math.abs(b[0])) for (int i = 0; i < a.length; i++) b[i] = a[i]; moves(n-1, a, b); } public static void main(String[] args) { int N = StdIn.readInt(); double[] a = new double[N+1]; double[] b = new double[N+1]; // read in input values for (int i = 1; i <= N; i++) a[i] = StdIn.readDouble(); // initialize a[0] = b[0] = a[1] + ... + a[N] for (int i = 1; i <= N; i++) a[0] += a[i]; b[0] = a[0]; // do the computation moves(N, a, b); // print out results for (int i = 1; i <= N; i++) System.out.printf("%6.2f\n", b[i]); System.out.printf("Difference: %.2f\n", b[0]); } }