貪欲法（グリーディ法）によって、常に最適解が得られる問題として適切なものはどれか。

解説

正解は「品物を分割して詰められるナップサック問題」です。貪欲法は、その時点で最も良く見える選択を繰り返して解を作る方法です。品物を分割できるナップサック問題では、重さあたりの価値が高い順に詰め、最後に入りきらない品物を分割して詰めれば最適解が得られます。「0-1ナップサック問題」では品物を分割できないため、単価の高い品物を優先すると容量に無駄が出て、最適解にならないことがあります。「巡回セールスマン問題」で最も近い都市へ進む貪欲法は、近似解しか得られません。「部分和問題」も、大きい数から選ぶ貪欲法では解を見逃すことがあります。これらには動的計画法や分枝限定法などを使います。