C++ 動的計画法（DP）ナップサック問題

典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ - Qiita

なんかややこしい。。 全部愚直に一から毎回計算すると大変なやつを、ところどころ覚えておいて表にでもしておけば、計算量減らせるやん的な雰囲気を醸し出しているやつ。何しろ上記で詳しく解説してくれている。大まかには分かったような気がする。

メモ化再帰というのと、漸化式というのとでやり方が異なるらしい。とはいえ実体的には大体同じようなことをしているらしい。メモ化というのはまじでただメモってるだけみたいな感じだったし、実際下記コードも細かく表にして再利用できるようにメモっている。だからきっと大体同じなんだろう。

#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

int n = 6;
int W = 9;
vector<int> weight = {2, 1, 3, 2, 1, 5};
vector<int> value = {3, 2, 6, 1, 3, 85};
vector<vector<int>> dp;

int main()
{
  dp.assign(n + 1, vector<int>(W + 1, 0));
  for (int i = 0; i < n; ++i)
  {
    for (int w = 0; w <= W; ++w)
    {
      if (w >= weight[i])
      {
        int next_value = dp[i][w - weight[i]] + value[i];
        dp[i + 1][w] = max(next_value, dp[i][w]);
      }
      else
      {
        dp[i + 1][w] = dp[i][w];
      }
    }
  }
  cout << dp[n][W] << endl;
}