DP(Dynamic Programming)をVue3.0 With TS & PrimeVUEで視覚化する

Kohei Kondo2020年12月7日3 min read

#DP #Vue #algorithm #Dynamic Programming

やること

典型的な動的計画法（Dynamic Programming)を使うナップサック問題をVue3.0の学習がてら視覚化していく

技術

Vue3.0
TypeScript
PrimeVUE

PrimeVUE

PrimeVUEはVue3.0に対応しており、良さげだったので使用。

あとせっかくなのでVueのCompositon APIで書いてみた。

余談：

Vue3.0のビルドが早くて驚いた。

また、Compositon APIを使うことにより型が厳密に定義できとても良いなと感じた。

ナップサック問題

今回のナップサックにつめこむ対象はこれら、

※Maxの重量は5とする

JavaScript


nup: [          
  { w: 2, v: 3 },
  { w: 1, v: 2 },
  { w: 3, v: 4 },
  { w: 2, v: 2 },
],
// w = weight
// v = 
valuemax_weight = 5;

愚直に再帰で全探索をするとO(2^n)かかってしまう。

そこで下記のような漸化式を作成し、

今回は上(indexが小さい)から計算してくので漸化式は

JavaScript


dp[0][j] = 0
dp[i+1][j] {
  dp[i][j] (j < nup[i].w)
  max(dp[i][j], dp[i][j-num[i].w] + nup[i].v)
}

このようになる。

こうすることによりO(nW)で計算ができるようになる。

C++で書くとこんな感じ

C++

void solve() {
  for (int i=0;i<n;i++) {
    for (int j=0; j<=totalWeight; j++) {
      if (j < weight[i]) {
        dp[i+1][j]=dp[i][j];
      } else {
        dp[i+1][j]=max(dp[i][j], dp[i+1][j-weight[i]] + value[i]);
      }
    }
  }
  cout << dp[n][totalWeight] << endl;
}