Logfiles

ARC073: D - Simple Knapsack

AtCoder ABC ARC

問題

D - Simple Knapsack

解説

DPで重さが整数のナップサック問題同様に解いたものの、Editorialによると全探索が本解の模様。

$dp_{i, j} := i個使ったとき重さi * w_i + jの価値の最大値$

とする。使うかどうかみている品物を $k$ として、 $0\le i\le k\le N)$ として、 $O(N^2 W_{余り})$ で解くことができる。dp配列は $k$ 番目の品物から次の $k+1$ 番目の品物を見るときに新規の配列とswapさせた。

コードは最大化が上下に来たりなど汚く、参考にされるべきものではない。DPとしても方針は簡素にできそうである。

constexpr int MaxRemW = 3 * 100 + 30;
vector<int64_t> w(101);
vector<int64_t> v(101);
vector<vector<int64_t>> dp(101, vector<int64_t>(MaxRemW + 1));
vector<vector<int64_t>> next_dp(101, vector<int64_t>(MaxRemW + 1));

int main() {
  int N; int64_t W; cin >> N >> W;
  rep(i, N) {
    cin >> w[i] >> v[i];
  }
  int64_t ans = 0;
  rep(k, N) {
    rep(i, 101) {
      dp[i].swap(next_dp[i]);
      next_dp[i].clear();
      next_dp[i].resize(MaxRemW + 1);
    }
    rep(i, k + 1) rep(j, MaxRemW) {
      maximize(next_dp[i][j], dp[i][j]);
      auto currW = i * w[0] + j;
      if (currW > W) continue;
      auto next_j = j + (w[k] - w[0]);
      if (next_j > MaxRemW) continue;
      auto nextW = (i + 1) * w[0] + next_j;
      if (nextW > W) continue;
      maximize(next_dp[i + 1][next_j], dp[i][j] + v[k]);
      maximize(ans, next_dp[i + 1][next_j]);
    }
  }
  cout << ans << "\n";
}