応用情報技術者アルゴリズムとデータ構造オリジナル・公式資料照合難易度★★★★☆
容量6のかばんに、品物(重さ,価値)=(2,3),(3,4),(4,5)を各1個まで入れる。次の0-1ナップサック法で得るdp[6]はどれか。dp[0..6]はすべて0で開始し、内側は大きい添字から小さい添字へ更新する。 for 各品物の(w,v)を上記の順に選ぶ for c を 6 から w まで1ずつ減らす dp[c] ← max(dp[c], dp[c-w]+v) endfor endfor
A
7
重さ2と3の組なら価値7ですが、重さ2と4の組で容量6以内の価値8を得られます。
B
8★ 正解
重さ2・価値3と重さ4・価値5を選ぶと重さ6、価値8で最大です。
C
9
価値9は重さ2の品物を3個選ぶ場合ですが、各品物は1個までという条件に反します。
D
12
すべての価値の合計は12ですが、重さも2+3+4=9となり容量6を超えます。
解説
内側を降順に更新すると、同じ品物を同じ回で複数回使うことを防ぎます。可能な組合せの最大は重さ2と4の価値8です。
根拠資料・確認情報
対応範囲：2026年度 応用情報技術者試験
資料確認日：2026-10-28