Aizu Online Judge 0170 Lunch

■0170 Lunch

全探索．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n;  
17.  String[] f;  
18.  int[] w, s;  
19.  int[] a, best;  
20.  double bestG;  
21.   
22.  void run(){  
23.   for(;;){  
24.    n=sc.nextInt();  
25.    if(n==0){  
26.     break;  
27.    }  
28.    f=new String[n];  
29.    w=new int[n];  
30.    s=new int[n];  
31.    for(int i=0; i<n; i++){  
32.     f[i]=sc.next();  
33.     w[i]=sc.nextInt();  
34.     s[i]=sc.nextInt();  
35.    }  
36.    solve();  
37.   }  
38.  }  
39.   
40.  void solve(){  
41.   a=new int[n];  
42.   best=new int[n];  
43.   for(int i=0; i<n; i++){  
44.    a[i]=i;  
45.   }  
46.   bestG=INF;  
47.   rec(0);  
48.   for(int e : best){  
49.    println(f[e]);  
50.   }  
51.  }  
52.   
53.  void rec(int j){  
54.   if(j==n){  
55.    int sumW=0;  
56.    int nW=0;  
57.    for(int i=n-1; i>=0; i--){  
58.     if(s[a[i]]<sumW){  
59.      return;  
60.     }  
61.     sumW+=w[a[i]];  
62.     nW+=(i+1)*w[a[i]];  
63.    }  
64.    double g=(double)nW/sumW;  
65.    if(g+EPS<bestG){  
66.     System.arraycopy(a, 0, best, 0, n);  
67.     bestG=g;  
68.    }  
69.    return;  
70.   }  
71.   
72.   for(int i=j; i<n; i++){  
73.    int t=a[i];  
74.    a[i]=a[j];  
75.    a[j]=t;  
76.    rec(j+1);  
77.    t=a[i];  
78.    a[i]=a[j];  
79.    a[j]=t;  
80.   }  
81.  }  
82.   
83.  void debug(Object... os){  
84.   System.err.println(Arrays.deepToString(os));  
85.  }  
86.   
87.  void print(String s){  
88.   System.out.print(s);  
89.  }  
90.   
91.  void println(String s){  
92.   System.out.println(s);  
93.  }  
94.   
95.  public static void main(String[] args){  
96.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
97.   new Main().run();  
98.  }  
99. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 String[] f;
 int[] w, s;
 int[] a, best;
 double bestG;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   f=new String[n];
   w=new int[n];
   s=new int[n];
   for(int i=0; i<n; i++){
    f[i]=sc.next();
    w[i]=sc.nextInt();
    s[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  a=new int[n];
  best=new int[n];
  for(int i=0; i<n; i++){
   a[i]=i;
  }
  bestG=INF;
  rec(0);
  for(int e : best){
   println(f[e]);
  }
 }

 void rec(int j){
  if(j==n){
   int sumW=0;
   int nW=0;
   for(int i=n-1; i>=0; i--){
    if(s[a[i]]<sumW){
     return;
    }
    sumW+=w[a[i]];
    nW+=(i+1)*w[a[i]];
   }
   double g=(double)nW/sumW;
   if(g+EPS<bestG){
    System.arraycopy(a, 0, best, 0, n);
    bestG=g;
   }
   return;
  }

  for(int i=j; i<n; i++){
   int t=a[i];
   a[i]=a[j];
   a[j]=t;
   rec(j+1);
   t=a[i];
   a[i]=a[j];
   a[j]=t;
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}