動的計画法を用いる機会が無くてナップザック問題すら解いたことが無いのでナップザック問題を解きました。入力 n w w1 v1 ... wn vnn 種類の荷物から自由に選択し、重さ w 以下で価値が最大となる組み合わせを選択する。 i 番目の荷物の重さは wi で価値は …