/****************************************************************************** * Compilation: javac Schedule.java * Execution: java Schedule n < data.txt * * This programs takes an integer command-line argument n, reads 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 k, double[] a, double[] b) { if (k == 0) return; moves(k-1, a, b); // flip whether or not a[k] is in the subset a[k] = -a[k]; a[0] += 2*a[k]; if (Math.abs(a[0]) < Math.abs(b[0])) for (int i = 0; i < a.length; i++) b[i] = a[i]; moves(k-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++) StdOut.printf("%6.2f\n", b[i]); StdOut.printf("Difference: %.2f\n", b[0]); } }