容量8のナップサックに、(重さ, 価値) が (2, 3)、(3, 4)、(4, 5)、(5, 6) の4つの品物から選んで入れる。各品物は1つずつしかなく、分割できない。重さの合計が8以下で、価値の合計の最大値はいくらか。

正解：C. 10

重さ3と5の品物を選ぶと重さ8で価値は 4 + 6 = 10 になり、これが最大です。重さ2と5(価値9)や3と4(価値9)も入りますが10には届かず、3つ選ぶと最も軽い 2 + 3 + 4 でも9で容量を超えます。重さあたりの価値の高い順に詰める貪欲法では、重さ2と3(価値7)を入れた後に残り3の容量に入る品物がなく、7で止まります。動的計画法では「容量 c までで達成できる最大の価値」を品物ごとに表で更新し、品物の数 n と容量 W に対して O(nW) で最適な値が求まります。

• A. 重さあたりの価値の高い順に詰める貪欲法の結果で、最適ではありません。
• B. 重さ2と5、または3と4の組み合わせの価値で、最大ではありません。
• C. 正しい。重さ3と5の品物で、容量8をちょうど使い価値10になります。