• ビットDP(bit DP)の考え方 集合に対する動的計画法
• 「bitDPで巡回セールスマンを解く」の解説がよくわからなかったのでさらに解説【python実装】

この問題は、以下の bitDP で解くことができます。

• \(dp[S][i] = \{\) 既に配置したアイテムの集合が \(S\) で、そのうち最後に配置したアイテムが \(i\) であるときの、既に確定した評価値の総和の最大値 \(\}\)

bitDP の形としては巡回セールスマン問題とよく似た形をしています。
しかし、「アイテムを既に \(c\) 個置いた状態で、アイテム \(i\) の次にアイテム \(j\) を置く時の評価関数の増分」が \(c,i,j\) 全てに依存することに注意してください。

\(S\) から既に配置されたアイテムの個数を抽出することで、次にアイテム \(j\) を置いた時の評価値の増分を求めることができます。

時間計算量は \(O(2^NN^2)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

using ll=long long;

ll gap(ll x,ll y){
  return max(x,y)-min(x,y);
}

int main(){
  int n;
  cin >> n;
  vector<ll> p(n),w(n-1);
  for(auto &nx : p){cin >> nx;}
  for(auto &nx : w){cin >> nx;}
  vector<vector<ll>> dp(1<<n,vector<ll>(n,-8e18));
  for(int i=0;i<n;i++){
    dp[1<<i][i]=0;
  }
  for(int i=0;i<(1<<n);i++){
    int pc=__builtin_popcount(i)-1;
    for(int j=0;j<n;j++){
      if(dp[i][j]<0){continue;}
      for(int k=0;k<n;k++){
        if(i&(1<<k)){continue;}
        dp[i|(1<<k)][k]=max(dp[i|(1<<k)][k],dp[i][j]+gap(p[j],p[k])*w[pc]);
      }
    }
  }
  
  ll res=0;
  for(int j=0;j<n;j++){
    res=max(res,dp[(1<<n)-1][j]);
  }
  cout << res << "\n";
  return 0;
}