No.4

すべてのおもりの重さの合計の半分の重さを作れるかどうかを調べる.

$i$ 番目のおもりまで調べたときにおもりの重さの合計 $W$ を作れるかどうかを $B(i, W)$ とすると,

$$B(i, W) = B(i - 1, W) \land B(i - 1, W + W_i)$$

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