Knapsack 2 [Educational DP Contest / DP まとめコンテスト E]

https://atcoder.jp/contests/dp/tasks/dp_e

前提知識

• 動的計画法

解説

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

ナップサック問題のよくある変形。
状態として保持する物を変形して解く。
というより、解く流れとしては、

1. dp[N][W]では状態数は無理
2. dp[N][V]ならちょうどいいから、こっちで考える

みたいな制約から考える場合が（自分は）多い。
なので、
dp[i][val] := i番目までの商品を入れて、価値の総和がvalである場合の重さの総和の最小値
を解く。
更新は、一般的なナップサックとほぼ同じ形になる。
最後にdp[N][val]≦Wを満たせば、その価値にできるので、満たす中でのvalの最大値が答え。

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