解説

動的計画法で解きます。

$dp[i][j]\coloneqq$ $i$ 個目の砂糖まで見て総重量が $j\space [\mathrm{g}]$ となる最小の金額

とします。

$dp[0][0]=0$、他を十分に大きい数で初期化しておきます。

$X \space [\mathrm{g}]$ 以上に注意すると、配るDPで $k=\min(j+m_i,\space X)$ として

$\begin{cases} dp[i+1][j]=dp[i][j]&(\text{使わない場合})\\dp[i+1][k]=\min(dp[i+1][k],\space dp[i][j]+v_i)&(\text{使う場合})\end{cases}$

と遷移することができ、計算量は $O(NX)$ です。

よってこの問題が解けました。

余談

この問題はナップサック問題の亜種であるので、dp配列を使い回すことができます。

$j$ を大きい方から回していくことで実装することができます。

使い回すことでメモリと実装量の削減につながるので覚えておくとよいでしょう。