選ぶことのできる荷物の重さの合計の最大値を \(R\) と表します。
はじめ、\(R=W\) です。
\(i=N,N-1,\dots,1\) の順に、荷物 \(i\) を選ぶかどうかを決めていきます。
\(R < W_i\) のとき、荷物 \(i\) を選ぶことはできません。
\(W_i \leq R\) のとき、荷物 \(i\) を選ばないならば、制約より \(\sum_{j=1}^{i-1}W_j \leq R\) なので、荷物 \(1,2,\dots,i-1\) をすべて選ぶことができます。
荷物 \(i\) を選ぶならば、\(R\) は \(R-W_i\) に更新されます。
選べる価値の合計を \(2\) つの場合でそれぞれ比較して大きい方を採用します。
これを再帰的に行うことで答えを \(O(N)\) で求めることはできます。