おもりの重さの合計を \(S\) とすると, \(S\) が奇数の場合はそもそも半分にできないので impossible である.

\(i\) 番目のおもりまで見たときに合計の重さが \(j\) になることがあるかどうかを \(B(i, j)\) とすると,

\[B(i, j) = B(i-1, j) \lor B(i-1, j+Wi)\]

となる. これを DP で計算し, \(B(N, S/2)\) を見る.