E - Knapsack 2

キーワード

DP
EDPC

解説

$i=0,1,\dots,N, ~ j=0,1,\dots,V$ に対して、 $dp_{i,j}$ を次のように定義する。(ただし、 $V = \sum{v_i}$ )

$i$ 番目までの品物から価値の総和が $j$ 以上となるように選んだときの重さの最小値

dp_{0,j} = \begin{cases} 0 & (j = 0) \\ \infty & (j > 0) \end{cases}

と初期化する。 $i$ 番目の品物まで使って良いとき、 $i$ 番目のしなものを使う場合と使わない場合の二通り考えられる。

使わない場合は、 $i-1$ 番目までの品物で、価値 $j$ を達成できるため、 $i-1$ 番目まで使った時の最小重みと等しい。
使う場合は、 $i-1$ 番目までの品物で、価値 $j-v_i$ を達成できる最小重みに $w_i$ を加えたもの。

よって次のような漸化式が立てられる。

dp_{i,j} = \begin{cases} dp_{i-1,j} & (j < v_i) \\ \min\{dp_{i-1,j}, dp_{i-1,j-v_i} + w_i\} & (j \geq v_i) \end{cases}

最終的な答えは、 $dp_{N,j} \leq W$ を満たす最大の $j$ となる。 $dp_{N,j}$ は $j$ について単調増加であるため、二分探索で求めることもできる。

提出コード

int main() {
    int n, w; cin >> n >> w;
    vector<int> W(n), V(n); rep(i,0,n) cin >> W[i] >> V[i];
    vector<vector<ll>> dp(n+1, vector<ll>(MAX, 1e18));
    dp[0][0] = 0;
    rep(i,1,n+1) {
        rep(j,0,MAX) {
            dp[i][j] = dp[i-1][j];
            if(j-V[i-1] >= 0) dp[i][j] = min(dp[i][j], dp[i-1][j-V[i-1]] + W[i-1]);
        }
    }
    rrep(j,MAX-1,0) if(dp[n][j] <= w) {
        cout << j << endl;
        break;
    }
}

D - Knapsack 1 F - LCS