001package algs14;
002import java.util.Arrays;
003import stdlib.*;
004/* ***********************************************************************
005 *  Compilation:  javac Exponential.java
006 *  Execution:    java Exponential N
007 *
008 *  A program with exponential running time. Read in N integers
009 *  and find the subset whose sum is closest to 0.
010 *
011 *  Limitations
012 *  -----------
013 *     - we assume no sum of N integers will overflow a int
014 *
015 *************************************************************************/
016
017public class XExponential {
018
019        public static double timeTrial(int N, int[] a) {
020                Stopwatch s = new Stopwatch();
021
022                // find subset closest to 0
023                long best = Long.MAX_VALUE;
024                int stop = 1 << N;
025                for (int n = 1; n < stop; n++)  {
026                        long sum = 0;
027                        for (int i = 0; i < N; i++) {
028                                if (((n >> i) & 1) == 1) sum = sum + a[i];
029                        }
030                        if (Math.abs(sum) < Math.abs(best)) best = sum;
031                }
032                //System.out.println(best);
033                return s.elapsedTime();
034        }
035
036
037        public static void main(String[] args) {
038                int MAX = 28;
039                int[] a = new int[MAX];
040                for (int i = 0; i < MAX; i++)
041                        a[i] = StdRandom.uniform (Integer.MIN_VALUE, Integer.MAX_VALUE);
042                StdOut.println(Arrays.toString (a));
043
044                StdOut.format("%7s %7s %4s\n", "size", "time", "ratio");
045                double prev = timeTrial(10, a);
046                for (int N = 1; N < MAX; N += 1) {
047                        double curr = timeTrial(N, a);
048                        StdOut.format("%7d %7.2f %4.2f\n", N, curr, curr / prev);
049                        prev = curr;
050                }
051        }
052}