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}