No.527

$i$ 番目の荷物まで見たときに容積合計が $w$ となる場合最大価値を $A(i, w)$ とすると,

$$A(i, w) = \max(A(i-1, w), A(i-1, w-w_i)+v_i)$$

となる. これを計算して $A(N, w) = V$ となる $w$ の最小値を求めればそれが $W$ の最小値である.

$A(i, w) = V^{\prime}$ ($V^{\prime} \gt V$) となる $w$ が存在するなら, その最小値を $w^{\prime}$ とすると $w^{\prime}-1$ が $W$ の最大値である. 存在しないならば $W$ の最大値は特定できない.