Problem 0170 : Lunch

Problem 0170 : Lunch
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0170

• 問題概要

縦に食べ物をつんで、潰れずにかつ、重心を低くするか。
潰れやすさと重さが与えられる

• 解法

その置きかたで潰れないか全通り試す。
その中で１番重心が低いものを出す。

潰れるかどうか試すときにDPっぽくすることが重要。
そうじゃないとオーダーがでかくなる（多分。

上から二番目のものからみていって、上にのってる食べ物の重さの合計をふやしながら、下に下がっていく。

• ソース

#include<iostream>
#include<algorithm>
#include<string>

#define INF 1000000000

using namespace std;

main(){

  int n;

  while(cin >> n){
    if(n==0)break;
    string index[n];
    int w[n], s[n], order[n], all = 0;

    for(int i=0; i<n; i++){
      cin >> index[i] >> w[i] >> s[i];
      all += w[i];
      order[i] = i;
    }
    
    double min = INF;
    int ans[n];

    do{
      int sum = 0;
      bool flag = false;
      for(int i=1; i<n; i++){
	sum += w[order[i-1]];
	if(sum > s[order[i]]){
	  flag = true;
	  break;
	}
      }
      if(flag){
	continue;
      }
      sum = 0;
      for(int i=0; i<n; i++){
	sum += (n-i)*w[order[i]];
      }
      double G = (double)sum /(double)all;
      
      if(min>G){
	min = G;
	for(int i=0; i<n; i++){
	  ans[i] = order[i];
	}
      }
    }while(next_permutation(order, order+n));
    
    for(int i=n-1; i>=0; i--){
      cout << index[ans[i]] << endl;
    }
  }
}