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