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;
}