AOJ 0170 Lunch

404 Not Found

nは高々10なので順列で生成してもいいんだろうけど360万ループ*重心とかの判定計算とかは効率化しないとTLEしそう。

ということでバックトラック解法

#include <iostream>
#include <vector>
using namespace std;

vector<int> choice;
string name[10];
int weight[10];
int s[10];
bool done[10];
int n;
pair<double,vector<int> > ret;

void bt(){
	int test;
	for(int i=0;i<choice.size();i++){
		test = 0;
		for(int j=i+1;j<choice.size();j++){
			test+=weight[choice[j]];
		}
		if(s[choice[i]] < test)return;
	}
	if(choice.size() == n){
		double G=0,DIV=0;	
		for(int i=0;i<choice.size();i++){
			G += (i+1)*weight[choice[i]];
			DIV += weight[choice[i]];
		}
		ret = min(ret,make_pair(G/DIV,choice));
	}
	
	for(int i=0;i<n;i++){
		if(!done[i]){
			done[i] = true;
			choice.push_back(i);
			bt();
			choice.pop_back();
			done[i] = false;
		}
	}
}

int main(){
	while(cin >> n, n){
		ret = make_pair(1<<21,0);
		for(int i=0;i<n;i++){
			cin >> name[i] >> weight[i] >> s[i];
		}
		bt();
		for(int i=0;i<ret.second.size();i++){
			cout << name[ret.second[i]] << endl;
		}
	}
}