Schedule.java

Below is the syntax highlighted version of Schedule.java from §2.3 Recursion.

/******************************************************************************
 *  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]);
    }
}