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; }