Knapsack 2 Educational DP Contest-E問題

問題文

$N$個の品物があります．品物には$1, 2, ...,N$と番号が振られています．各$i(1\leq i \leq N)$について，品物$i$の重さは$w_i$で，価値は$v_i$です．太郎君は，$N$個の品物の内いくつかを選び，ナップサックに入れて持ち帰ることにしました．ナップサックの容量は$W$であり，持ち帰る品物の重さの総和は$W$以下でなければなりません．太郎君が持ち帰る品物の価値の総和の最大値を求めてください．
$1\leq N \leq 100$
$1\leq W \leq 10^9 $
$1\leq w_i \leq W$
$1\leq v_i \leq 10^3$

考察

$dp[i][j] = $前から$i$個までの中から任意の数選んだとき，価値の和を$j$とするために必要な最小のコスト，とします．
$dp[i][j] = $前から$i$個までの中から総コスト$j$以下になるように任意の数選んだ時，価値の総和の最大値，
という普通のナップサック問題の解法で解いてしまうと，計算量のオーダーが$O(NW)$となるため，計算量の最大値が$100\times W_{max}=10^{11}$となってしまいます．これを今回の解法で解くと，計算量のオーダーが$O(N\sum_i v_i)$となり，計算量の最大値が$100\times 10^3 \times 100=10^7$で処理が$2$秒以内に間に合います．

$$dp[i][j]=min(dp[i-1][j],\quad dp[i-1][j-v[i-1]]+w[i-1])$$

前から$i$番目の品物を選ぶ場合と選ばない場合を比較し，総コストが小さいほうを$dp[i][j]$に採用していきます．$i$番目の品物を選ばない場合は$dp[i-1][j]$で$i-1$番目までから選び，価値$j$を達成する最小の総コストをそのまま$dp[i][j]$の候補とします．$i$番目を選ぶ場合は，$i-1$番目までから好きに品物を選び，総価値$j-v[i-1]$を達成するための最小のコストに$i$番目のコスト$w[i-1]$を加えたものを$dp[i][j]$の二つ目の候補とします．ただし，$j-v[i-1]<0$のときは，価値の総和が負になることはないので候補から外します．

int main(){
    ll n, W;
    cin >> n >> W;
    vector<ll> w(n), v(n);
    ll sv = 0;
    ll INF = 101010101010;
    for(ll i=0; i<n; i++){
        cin >> w[i] >> v[i];
        sv+=v[i];
    }
    vector<vector<ll>> dp(n+1, vector<ll>(sv+1, INF));
    for(ll i=0; i<=n; i++) dp[i][0] = 0;
    for(ll i=1; i<=n; i++){
        for(ll j=0; j<=sv; j++){
            dp[i][j] = dp[i-1][j];
            if(j-v[i-1]>=0) chmin(dp[i][j], dp[i-1][j-v[i-1]]+w[i-1]);
        }
    }
    for(ll i=sv; i>=0; i--){
        if(dp[n][i]<=W){
            cout << i << endl;
            break;
        }
    }

    return 0;
}