はまやんはまやんはまやん

hamayanhamayan's blog

前提知識

動的計画法

解説

https://atcoder.jp/contests/dp/submissions/3946683

一般的なナップサック問題。
dp[i][tot] := i番目までの商品を入れて、重さの総和がtotである場合の価値の総和の最大値
ナップサック問題ではこの形がベースになることが多いので、覚えよう。
行動としては取る取らないの2択があるので、それを実装する。
ナップサック問題をDPで解くやり方は、多数解説されているので、読んで覚えよう。

int N, W, w[101], v[101];
ll dp[101][201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> W;
    rep(i, 0, N) cin >> w[i] >> v[i];
 
    rep(i, 0, N) rep(tot, 0, W) {
        chmax(dp[i + 1][tot], dp[i][tot]);
        chmax(dp[i + 1][tot + w[i]], dp[i][tot] + v[i]);
    }
 
    ll ans = 0;
    rep(tot, 0, W + 1) chmax(ans, dp[N][tot]);
    cout << ans << endl;
}