Old Knapsack

$H<w_i\leq W$なる荷物を1つ選択した後、その荷物より下にある荷物に対して、大きさの総和が$W-w_i$以下になるように荷物を選択して価値の総和を最大化するKnapsack問題を考えると、

$H<w_i\leq W$なる全ての$i$についての、((上記のKnapsack問題の答え)$+v_i$) の最大値が問題の答えです。

愚直に実装すると間に合わないので工夫して考えます。

---

逆順に見ることを考えます。$w$と$v$の数列を両方とも逆順にして、(上の荷物は下に、下の荷物は上になるように並び替えて、)

$dp[i][j] = ($上から$i-1$番目の荷物まで見て、大きさの総和が$j$以下になるように荷物を選んだときの価値の総和の最大値$)$

をそれぞれの$i$、$j$について前計算します。

すると、$ans=0$を初期値として、$H<w_i\leq W$なる荷物それぞれに対し、
$ans$ ← $max(ans, dp[i][W-w_i]+v_i)$
のように答えを更新することで、$O(NW)$でこの問題の答えを求めることができます。