Knapsack Expect i-th

$dp_+[i][j]:=$前から$i$番目までの荷物を見て，重さの総和が$j$であるときの価値の総和の最大値
$dp_-[i][j]:=$後ろから$i$番目までの荷物を見て，重さの総和が$j$であるときの価値の総和の最大値
とします．この$2$つの配列の各要素は動的計画法により$O(NW)$で計算することができます．

$i$番目の荷物を含めない場合の計算方法を考えてみましょう．
これは，前から$(i-1)$番目まで荷物を見た結果と， 後ろから$(N-i)$番目まで荷物を見た結果より計算することができます．
また，前から$(i-1)$番目まで見て重さの総和が$k$だった場合， 後ろから$(N-i)$番目まで見た時に許容される容量の最大値は$(W-k)$となります．

よって各$i$について以下の値を計算したものが答えとなります．

• $\max_{0 \leq k \leq W} (dp_+[i-1][k] + dp_-[N-i][W-k])$

問題全体としての時間計算量は$O(NW)$でこの問題の条件下では十分高速です．