アルゴリズム道中記〜20240411〜

A19 - Knapsack 1

#include <bits/stdc++.h>
#define print(x) cout << x << endl;
#define rep(i, s, n) for (long long i = s; i < (long long)(n); i++)
using namespace std;
using ll = long long;

int main() {
  ll N, W;
  cin >> N >> W;
  vector<ll> w(N+1), v(N+1); 
  vector<vector<ll>> dp(N+1, vector<ll>(W+1, -1));
  rep (i, 1, N+1)
    cin >> w[i] >> v[i];
  dp[0][0] = 0;
  rep (i, 1, N+1)
  {
    rep (k, 0, W+1)
    {
      if (k < w[i]) dp[i][k] = dp[i-1][k];
      else dp[i][k] = max(dp[i-1][k], dp[i-1][k - w[i]] + v[i]);
    }
  }
  ll ans = 0;
  rep (i, 0, W+1)
    ans = max(ans, dp[N][i]);
  print(ans);
}

ナップザックDPですね。DPテーブルが、値をメモしており、Indexに値をたし引きしてアクセスするという考え方が、だんだんとわかってきたような気がします。今回、一度目は写経でしたが、二度目は暗記して打ち込みました。まずは暗記してしまった方が、理解が早いかもしれません。