AOJ:0170 Lunch
全探索です。
計算量は、10![候補生成の計算量] * 10[全ての食物が潰れないかのチェックの計算量] ≒ 3.0*10^7
#define _USE_MATH_DEFINES #define MAX_N 1000000 #include <iostream> #include <sstream> #include <cmath> #include <algorithm> #include <queue> #include <stack> #include <limits> #include <map> #include <string> #include <cstring> #include <set> #include <deque> #include <bitset> using namespace std; typedef long long ll; typedef pair<int,int> P; static const double eps = 1e-8; struct FOOD{ string name; int w; int s; }; bool checkWeight(const struct FOOD* food,const int* table,int n){ int sum=0; for(int i=n-1,j=n-2;i>=1,j>=0;i--,j--){ sum += food[table[i]].w; if(food[table[j]].s < sum) return false; } return true; } double getG(const struct FOOD* food,const int* table,int n){ double G=0; double sum=0; for(int i=0;i<n;i++){ G += (double)food[table[i]].w * (i+1); sum += (double)food[table[i]].w; } return G / sum; } int main(){ int n; while(~scanf("%d",&n)){ if(n==0) break; struct FOOD* food = new struct FOOD[n]; for(int i=0;i<n;i++){ char buf[64]; int w,s; scanf("%s %d %d",buf,&w,&s); food[i].name = buf; food[i].s = s; food[i].w = w; } int* table = new int[n]; for(int i=0;i<n;i++) table[i] = i; int* res = new int[n](); double minG = 1000000.0; do{ double tmpG; if(checkWeight(food,table,n) && minG > (tmpG = getG(food,table,n))){ copy(table,table+n,res); minG = tmpG; } }while(next_permutation(table,table+n)); for(int i=0;i<n;i++){ printf("%s\n",food[res[i]].name.c_str()); } delete[] food; delete[] table; } }