0170-Lunch
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0170
全探索を考えるとO(n!)となるが、n<=10より間に合うことが分かる。
従って全探索で実装すればよい。
struct food{ char name[23]; int w; int s; }; food data[10]; int res[10],tmp,t; int wsum=0; double js,ts; int main(int argc,char *argv[]){ int n; int p[10]; for(;;){ scanf("%d",&n);if(n==0) return 0; tmp=INT_MAX; wsum=0; for(int i=0;i<n;i++){ scanf("%s %d %d",data[i].name,&data[i].w,&data[i].s); wsum+=data[i].w; } js=999999; for(int i=0;i<n;i++) p[i]=i; do{ t=data[p[n-1]].w; for(int i=n-2;i>=0;i--){ if(t>data[p[i]].s) {t=-1;break;} t+=data[p[i]].w; } if(t!=-1){ tmp=0; for(int i=0;i<n;i++){ tmp+=data[p[i]].w*(i+1); } ts=(double)tmp/(double)wsum; if(ts<js){ js=ts; for(int i=0;i<n;i++){ res[i]=p[i]; } } } } while(std::next_permutation(p,p+n)); for(int i=0;i<n;i++) printf("%s\n",data[res[i]].name); } return 0; }