動的計画法で解きます.
現在の蔵の位置, 通った蔵(ビット管理), を管理するDP用の二次元配列を作って, 解きます.
再帰＋メモ化でやりました.
プログラム
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
#define INF 999999999.0
typedef pair< double,vector<int> > P;
int n;
int name[15],x[15],w[15];
P dp[15][1<<15];
P solve(int idx,int used,int weight){
P res(0,vector<int>());
res.second.push_back(name[idx]);
if(used == (1<<n)-1) return res;
if(dp[idx][used].first != INF) return dp[idx][used];
res.first = INF;
for(int i=0;i<n;i++){
if((used & (1<<i)) == 0){
P tmp = solve(i,used|(1<<i),weight+w[i]);
tmp.first += abs(x[i] - x[idx]) / (2000.0 / (70+weight));
if(res.first > tmp.first){
res = tmp;
}
}
}
res.second.insert(res.second.begin(),name[idx]);
return dp[idx][used] = res;
}
int main(void){
cin>>n;
for(int i=0;i<n;i++){
cin>>name[i]>>x[i]>>w[i];
w[i] *= 20;
}
for(int i=0;i<n;i++){
for(int j=0;j<(1<<n);j++){
dp[i][j] = P(INF,vector<int>());
}
}
P ans(INF,vector<int>());
for(int i=0;i<n;i++){
P tmp = solve(i,1<<i,w[i]);
if(ans.first > tmp.first) ans = tmp;
}
for(int i=0;i<n-1;i++) cout<<ans.second[i]<<" ";
cout<<ans.second[n-1]<<endl;
return 0;
}
